209. Minimum Size Subarray Sum

  • 29.4%

https://leetcode.com/problems/minimum-size-subarray-sum/

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

1
2
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).


方法一:

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size();
if(n==0) return 0;
int res = INT_MAX;
int i=-1, j=0, sum=0;
while(j<n){
sum += nums[j++];
while(sum>=s){
res = min(res, j-i-1);
sum -= nums[++i];
}
}
return res==INT_MAX? 0 : res;
}
};

8ms, 14.16%, June.24th, 2016

https://leetcode.com/discuss/42143/4ms-o-n-8ms-o-nlogn-c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size(), start = 0, sum = 0, minlen = INT_MAX;
for (int i = 0; i < n; i++) {
sum += nums[i];
while (sum >= s) {
minlen = min(minlen, i - start + 1);
sum -= nums[start++];
}
}
return minlen == INT_MAX ? 0 : minlen;
}
};

学习区:

https://discuss.leetcode.com/topic/37844/o-n-template-for-minimum-size-subarray-sum-minimum-window-substring-longest-substring-without-repeating-characters

O(N) template for Minimum Size Subarray Sum & Minimum Window Substring & Longest Substring Without Repeating Characters

First , I will show you the solution of this problem,

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

Next, let me show you the solution to the problem “Minimum Window Substring”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
string minWindow(string s, string t) {
vector<int> v(128, 0);
for(auto c:t) v[c]++;
int start=0, end=0, counter=t.size();
int m_start=0, m_len=INT_MAX;
while(end<s.size()){
if(v[s[end]]>0) counter--;
v[s[end]]--;
end++;
/** loop from start to check whether we can find more short string **/
while(counter==0){
if(m_len>end-start){
m_start=start;
m_len=end-start;
}
v[s[start]]++;
if(v[s[start]]>0) counter++;
start++;
}
}
return m_len==INT_MAX ? "" : s.substr(m_start, m_len);
}
};

The solution for the problem “Longest Substring Without Repeating Characters” can also be solved in the

same pattern .

Here is the solution for “Longest Substring Without Repeating Characters”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> v(128, 0);
int start=0, end=0;
int m_len=INT_MIN;
while(end<s.size()){
if(v[s[end]]==0) m_len=max(m_len, end-start+1);
v[s[end]]++;
end++;
while(v[s[end]]>0){
v[s[start]]--;
start++;
}
}
return m_len==INT_MIN ? 0 : m_len;
}
};

As you can see, they all follow the same pattern !

This post deserves your up vote!


1ms, 16.03%, June.24th, 2016

https://leetcode.com/discuss/45449/accepted-clean-java-o-n-solution-two-pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
if(nums == null || nums.length == 0)
return 0;

int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;

while(j < nums.length){
sum += nums[j++];

while(sum >= s){
min = Math.min(min, j - i);
sum -= nums[i++];
}
}

return min == Integer.MAX_VALUE ? 0 : min;
}
}

47ms, 96.87%, June.24th, 2016

https://leetcode.com/discuss/36384/python-o-n-and-o-n-log-n-solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
total = left = 0
result = len(nums) + 1
for right, n in enumerate(nums):
total += n
while total >= s:
result = min(result, right - left + 1)
total -= nums[left]
left += 1
return result if result <= len(nums) else 0
谢谢你,可爱的朋友。