209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

这个运用尺取法,这个方法使用了lower_bound的方法，复杂度为$$ O(nlog n) $$

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        vector<int> sum(n + 1, 0);

        for(int i = 0; i < n; i++){
            sum[i + 1] = sum[i] + nums[i];
        }

        if(sum[n] < s)  return 0;
        int res = n;

        for(int b = 0; sum[b] + s <= sum[n]; b++){
            int t = lower_bound(sum.begin() + b, sum.begin() + n, sum[b] + s) - sum.begin();
            res = min(res, t - b);
        }
        return res;
    }
};

利用两个指针，此时的复杂度为$$ O(n) $$

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int b = 0, t = 0, sum = 0;
        int n = nums.size();
        int res = n + 1;
        for(;;){
            while(t < n && sum < s){
                sum += nums[t++];
            }

            if(sum < s) break;
            res = min(res, t - b);
            sum -= nums[b++];
        }
        if(res > n) res = 0;
        return res;
    }
};