题目链接：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).

这道题的要求是在含有n个正整数数组中找到子数组，使其元素之和大于等于给定正整数s，要使子数组长度最小，返回其长度，如果不存在返回0。

和Longest Substring Without Repeating Characters同样的思路，采用l和r两个指针。同时用sum变量记录l和r之间元素的和。r不断右移，sum加上当前r所指的元素。如果此时sum大于给定数字s，此时需要用sum减去l所指元素并同时令l右移直到sum刚好小于s。记录此时l和r区间长度（此时是左闭右开，而且sum是刚好小于s，因此为r-l+1）即可。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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