LeetCode209.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.

Example:

1
2
3
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:

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


Two Pointers

1

  • 设置两个指针,作为数组边界,右指针向右移动一格,记录当前数组总和;min_count初始化为最大值INT_MAX。
  • 循环判断。如果总和大于等于target,更新min_count;并缩小数组范围,左指针向右移动一格。
  • 如果没有更新过,最后返0.
  • O(n) time.

my code in cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int minSubArrayLen(int s, vector<int>& nums) {
int _slow = 0, _fast = 0, _sum = 0, _min_count = INT_MAX;
while (_fast != nums.size())
{
_sum += nums[_fast];
while (_sum >= s)//1.
{
_min_count = min(_min_count, _fast-_slow+1);
_sum -= nums[_slow];
_slow++;
}
_fast++;
}
return _min_count==INT_MAX?0:_min_count;//2.
}

细节

  1. 不用if,_slow指针会多移动几个,count会一直更新,做循环判断。
  2. 如果一次都没有更新,返回0。

Divide and Conquer

my code in cpp

参照53题分治法写的,但是有两个样例超时没通过,可能我的递归有问题。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int ret = minHelper(s, nums, 0, nums.size() - 1);
return ret==INT_MAX?0:ret;
}
private:
int minHelper(int s, vector<int>& nums, int l, int r)
{
if (l > r) return INT_MAX;//1.INT_MAX
int m = l + (r - l) / 2;
int lmin = minHelper(s, nums, 0, m - 1);
int rmin = minHelper(s, nums, m + 1, r);


//left mincount
int sum = nums[m], count = 1, mmin = INT_MAX;//2.count =1
for (int i = m - 1; i >= 0; i--)
{
if (sum >= s)//3.本身。所以入口判断。
{
mmin = min(mmin, count);
break;
}
sum += nums[i];
count++;
}

//right mincount
for (int i = m + 1; i <= r; i++)
{
if (sum >= s)
{
mmin = min(mmin, count);
break;
}
sum += nums[i];
count++;
}
if(sum>=s)
mmin = min(mmin, count);
return min(min(lmin,rmin),mmin);
}
};

output:Time Limit Exceeded

1
2
3
4
5
6
× Time Limit Exceeded
× 13/15 cases passed (N/A)
× testcase: '697439\n[5334,6299,4199,9663,8945,3566,9509,3124,6026,6250,7475,5420,9201,9501,38,5897,4411,6638,9845,161,9563,8854,3731,5564,5331,4294,3275,1972,1521,2377,3701,6462,6778,187,9778,758,550,7510,6225,8691,3666,4622,9722,8011,7247,575,5431,4777,4032,8682,5888,8047,3562,9462,6501,7855,505,4675,6973,493,1374,3227,1244,7364,2298,3244,8627,5102,6375,8653,1820,3857,7195,7830,4461,7821,5037,2918,4279,2791,1500,9858,6915,5156,970,1471,5296,1688,578,7266,4182,1430,4985,5730,7941,3880,607,8776,1348,2974,1094,6733,5177,4975,5421,8190,8255,9112,8651,2797,335,8677,3754,893,1818,8479,5875,1695,8295,7993,7037,8546,7906,4102,7279,1407,2462,4425,2148,2925,3903,5447,5893,3534,3663,8307,8679,8474,1202,3474,2961,1149,7451,4279,7875,5692,6186,8109,7763,7798,2250,2969,7974,9781,7741,4914,5446,1861,8914,2544,5683,8952,6745,4870,1848,7887,6448,7873,128,3281,794,1965,7036,8094,1211,9450,6981,4244,2418,8610,8681,2402,2904,7712,3252,5029,3004,5526,6965,8866,2764,600,631,9075,2631,3411,2737,2328,652,494,6556,9391,4517,8934,8892,4561,9331,1386,4636,9627,5435,9272,110,413,9706,5470,5008,1706,7045,9648,7505,6968,7509,3120,7869,6776,6434,7994,5441,288,492,1617,3274,7019,5575,6664,6056,7069,1996,9581,3103,9266,2554,7471,4251,4320,4749,649,2617,3018,4332,415,2243,1924,69,5902,3602,2925,6542,345,4657,9034,8977,6799,8397,1187,3678,4921,6518,851,6941,6920,259,4503,2637,7438,3893,5042,8552,6661,5043,9555,9095,4123,142,1446,8047,6234,1199,8848,5656,1910,3430,2843,8043,9156,7838,2332,9634,2410,2958,3431,4270,1420,4227,7712,6648,1607,1575,3741,1493,7770,3018,5398,6215,8601,6244,7551,2587,2254,3607,1147,5184,9173,8680,8610,1597,1763,7914,3441,7006,1318,7044,7267,8206,9684,4814,9748,4497,2239]'
× answer:
× expected_answer:
× stdout:

LC in cpp

建立一个比原数组长一位的sums数组,其中sums[i]表示nums数组中[0, i - 1]的和,然后我们对于sums中每一个值sums[i],用二分查找法找到子数组的右边界位置,使该子数组之和大于sums[i] + s,然后我们更新最短长度的距离即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minSubArrayLen(int s, vector<int>& nums) {
int res = INT_MAX, n = nums.size();
vector<int> sums(n + 1, 0);
for (int i = 1; i < n + 1; ++i)
sums[i] = sums[i - 1] + nums[i - 1];
for (int i = 0; i < n; ++i) {
int left = i + 1, right = n, t = sums[i] + s;
while (left <= right) {
int mid = left + (right - left) / 2;
if (sums[mid] < t) left = mid + 1;
else right = mid - 1;
}
if (left == n + 1) break;
res = min(res, left - i);
}
return res == INT_MAX ? 0 : res;
}
1
2
3
4
5
6
7
8
9
10
11
12
int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size(), len = INT_MAX;
vector<int> sums(n + 1, 0);
for (int i = 1; i <= n; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
for (int i = n; i >= 0 && sums[i] >= s; i--) {
int j = upper_bound(sums.begin(), sums.end(),sums[i] - s) - sums.begin();
len = min(len, i - j + 1);
}
return len == INT_MAX ? 0 : len;
}
Thanks for Support.