209Minimum Size Subarray Sum

O(n)滑动数组
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int minLen = INT_MAX;
        int left = 0,sum = 0;
        for(int i = 0;i < nums.size();++i) {
            sum+=nums[i];
            while(sum >= s){
                minLen = min(minLen,i-left+1);
                sum-=nums[left++];
            }
        }
        return minLen==INT_MAX? 0 : minLen; 
    }
};
    int minSubArrayLen(int s, vector<int>& nums) {
        int l = 0 , r = -1; // nums[l...r]为我们的滑动窗口
        int sum = 0;
        int res = nums.size()+1;
        while( l < nums.size() ){   // 窗口的左边界在数组范围内,则循环继续
            if( r + 1 < nums.size() && sum < s )
                sum += nums[++r];
            else // r已经到头 或者 sum >= s
                sum -= nums[l++];
            if( sum >= s )
                res = min(res, r-l+1);
        }
        if( res == nums.size() + 1 )
            return 0;
        return res;
    }
O(nlogn)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        vector<int> sums = accumulate(nums);
        int n = nums.size(), minlen = INT_MAX;
        for (int i = 1; i <= n; i++) { 
            if (sums[i] >= s) {
                int p = upper_bound(sums, 0, i, sums[i] - s);
                if (p != -1) minlen = min(minlen, i - p + 1);
            }
        }
        return minlen == INT_MAX ? 0 : minlen;
    }
private:
    vector<int> accumulate(vector<int>& nums) {
        int n = nums.size();
        vector<int> sums(n + 1, 0);
        for (int i = 1; i <= n; i++) 
            sums[i] = nums[i - 1] + sums[i - 1];
        return sums;
    }
    int upper_bound(vector<int>& sums, int left, int right, int target) {
        int l = left, r = right;
        while (l < r) {
            int m = l + ((r - l) >> 1);
            if (sums[m] <= target) l = m + 1;
            else r = m;
        }
        return sums[r] > target ? r : -1;
    }
};

• https://discuss.leetcode.com/topic/17063/4ms-o-n-8ms-o-nlogn-c/2