209.长度最小的子数组 (Medium)*

题目描述*

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

进阶*

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

代码*

滑动窗口或二分查找。开始就想出来滑动窗口，没想出来二分。二分就需要有序数组。可以定义 sums[i] 表示从 0 到 i 的和，这样就得到了有序数组。可以根据 sums 计算子数组和，即 sums[j] - sums[i - 1]。每次通过二分搜索查找满足 sums[j] - sums[i] >= s - nums[i] ==> sums[j] >= s - nums[i] + sums[i] 的位置，即左边界。

还有一种二分是构造递增数组 sums[i] 表示长度为 i 的连续最大和。对长度进行二分，求满足条件的最小长度。

滑动窗口二分查找前缀和对长度二分

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int l = 0, r = 0;
        int sum = 0;
        int res = INT_MAX;
        while(r < nums.size()) {
            if(sum + nums[r] < s) {
                sum += nums[r];
                r++;
            }else {
                if(r - l < res) {
                    res = r - l + 1;
                }
                sum = sum - nums[l];
                l++;
            }
        }
        return res == INT_MAX ? 0 : res;
    }
};

class Solution {
public:
    int binarySearch(vector<int>& sums, int l, int r, int target) {
        // 主要复习搜索数组左边界
        while(l < r) {
            int mid = l + (r - l) / 2;
            if(sums[mid] >= target) {
                r = mid;
            }else if(sums[mid] < target) {
                l = mid + 1;
            }
        }
        if(l == sums.size()) {
            return -1;
        }
        return l;
    }
    int minSubArrayLen(int s, vector<int>& nums) {
        int len = nums.size();
        if(len == 0) {
            return 0;
        }
        vector<int> sums(nums.size(), 0);
        sums[0] = nums[0];
        for(int i = 1; i < len; i++) {
            sums[i] = sums[i - 1] + nums[i];
        }
        int res = INT_MAX;
        for(int i = 0; i < len; i++) {
            int curSum = s - nums[i];
            // 二分查找的目标是 sums[j] - sums[i] >= curSum ==> sums[j] >= sums[i] + curSum
            int pos = binarySearch(sums, i, len, s - nums[i] + sums[i]);
            if(pos != -1) {
                cout << pos << " " << i << endl;
                res = (res > pos - i + 1 ? pos - i + 1 : res);
            }
        }
        return res == INT_MAX ? 0 : res;
    }
};

class Solution {
public:
    int getMaxSum(vector<int>& nums, int tarLen) {
        int len = nums.size();
        int sum = 0;
        for(int i = 0; i < tarLen; i++) {
            sum += nums[i];
        }
        int maxSum = sum;
        for(int i = tarLen; i < len; i++){
            sum += nums[i];
            sum -= nums[i - tarLen];
            maxSum = (maxSum >= sum ? maxSum : sum);
        }
        return maxSum;
    }
    int minSubArrayLen(int s, vector<int>& nums) {
        int len = nums.size();
        if(len == 0) {
            return 0;
        }
        int minLen = 0, maxLen = len;
        int mid;
        int res = -1;
        while(minLen <= maxLen) {
            mid = minLen + (maxLen - minLen) / 2;
            if(getMaxSum(nums, mid) >= s) {
                maxLen = mid - 1;
                res = mid;
            }else {
                minLen = mid + 1;
            }
        }
        return res == -1 ? 0 : res;
    }
};

最后更新: July 23, 2022