导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-209.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,找到 sum ≥ s的长度最短的子数组。如果不存在,则返回0.
例如,给出数组 [2,3,1,2,4,3]s = 7,子数组 [4,3] 为所求。
更多练习:
如果你已经找到了 O(n) 的解法,试着编出另外一种时间复杂度为O(nlogn)的解法。

利用滑动窗口法,时间复杂度为O(n):

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) {
int start = 0, end = 0;
int len = nums.length;
int sum = 0, minLen = len + 1;

while (start < len) {
while (end < len && sum < s) {
sum += nums[end++];
if (end == len)
return minLen <= len ? minLen : 0;
}
minLen = Math.min(minLen, end - start);
sum -= nums[start];
start++;
}
return minLen <= len ? minLen : 0;
}
}

对于O(nlogn)的办法,考虑对于长度为n的数组,解的返回值共有0到n共n+1种可能。因为可以在O(n)的时间内,判断出对于给定的长度i,能否在数组中找到和大于s的子数组。因此可以对0到n+1采用二分法,每次取中值,判断该长度下是否可以找到满足的解。
例如,给出数组nums,长度为5,和s。首先取left=0,right=5,则mid=2,判断nums中是否存在长度为2的子数组,其和大于等于s,如果存在,更新结果为2,left=0,right=mid-1=1,循环;如果不存在,left=mid+1=3,right=5,循环判断。直到left>right为止:

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
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int start = 0, end = nums.length;
int minLen = 0;

while (start <= end) {
// 判断是否存在mid个元素的子数组,其和大于等于s
int mid = (start + end) / 2, sum = 0, index = 0;

while (index < mid)
sum += nums[index++];
for (int i = 0; index < nums.length && sum < s; i++) {
sum -= nums[i];
sum += nums[index++];
}

if (sum >= s) {
minLen = mid;
end = mid - 1;
} else start = mid + 1;
}

return minLen;
}
}

参考:
http://bookshadow.com/weblog/2015/05/12/leetcode-minimum-size-subarray-sum/?utm_source=tuicool&utm_medium=referral