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.

More practice: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

求和等于给定值的最短子数组，最开始想用用双重循环把所有大于等于给定值的子数组都穷举出来然后寻找最短子数组，但是考虑到时间复杂度为O(n^2)，于是进一步考虑优化方案。

最终，在参考了讨论区之后，我打算引入滑动窗口的思想来解决问题。

初始窗口为[low,high],low,high初始值均为0，窗口内部不包含元素;因为此时窗口sum==0< s,所以上界high向右移动，直到sum大于等于s时，我们先计算长度并进行比较，之后尝试舍弃窗口的第一个元素，如果还大于等于s，则继续舍弃，直到找到和等于给定值的最短子数组。代码如下:

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        if(nums.empty())
            return 0;
        int i=0,j=0,size=nums.size(),sum=0,min_size=INT_MAX;
        for(i=0;i<size;i++){
            while(sum<s){
                sum+=nums[++j];
            }
            min_size=min(min_size,j-i+1);
        }
        return min_size==INT_MAX ? 0:min_size;
    }
};

这里需要注意的是，虽然for循环内部还有一个while循环，但并不意味着时间复杂度为O(n^2)，因为我们考虑最坏情况，sum每加上一个nums[i]，就要进入内循环执行一次sum-=nums[low++],那么也是执行n次减法运算，总时间复杂度为O(2n)，也就是说这个算法依然是线性阶的时间复杂度。