What hurts more, the pain of hard work or the pain of regret?

0%

minimum-size-subarray-sum-209

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;
}
};
请我喝杯咖啡