minimum-size-subarray-sum-209

发表于 更新于 分类于 阅读次数： 阅读次数： Disqus：

problem

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.

题解

参考，滑动窗口，跟之前Data Structure课上的online算法有点像，链接

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int len = nums.size();
        if(len == 0) return 0;
        int minlen = INT_MAX;
        int sum = 0;
        
        int left = 0;
        int right = -1;
        while(right < len)
        {
            while(sum < s && right < len)
                sum += nums[++right];
            if(sum >= s)
            {
                minlen = minlen < right - left + 1 ? minlen : right - left + 1;
                sum -= nums[left++];
            }
        }
        return minlen > len ? 0 : minlen;
    }
};