来自Leetcode第209题长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
1
2
3
| 输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
|
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
丢人写法
双指针，一开始按照等于做的直接错了，是大于等于，此外还要注意临界条件，当nums[right] >= s时，可以直接返回1；当if(minlen == Integer.MAX_VALUE || right - left == len)时，意味着没满足条件，应当返回0.
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
| public int minSubArrayLen(int s, int[] nums) {
if(nums.length == 0)
return 0;
int minlen = Integer.MAX_VALUE;
int left = 0, right = 0,len = nums.length;
int sum = 0;
while(right < len){
if(nums[right] >= s){
return 1;
}
sum += nums[right];
if(sum >= s){
while(sum >= s && left < right) {
if (minlen > right - left + 1) {
minlen = right - left + 1;
}
sum -= nums[left];
left++;
}
}
right++;
}
if(minlen == Integer.MAX_VALUE || right - left == len)
return 0;
return minlen;
}
|
精简双指针
用双指针 left 和 right 表示一个窗口。
- right 向右移增大窗口，直到窗口内的数字和大于等于了
s。进行第 2 步。
- 记录此时的长度，left 向右移动，开始减少长度，每减少一次，就更新最小长度。直到当前窗口内的数字和小于了
s，回到第 1 步。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int left = 0;
int right = 0;
int sum = 0;
int min = Integer.MAX_VALUE;
while (right < nums.length) {
sum += nums[right];
right++;
while (sum >= s) {
min = Math.min(min, right - left);
sum -= nums[left];
left++;
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
|
二分查找
来自
题目中，我们要寻找连续的数字和大于等于 s 的最小长度。那么，我们可以对这个长度采取二分的方法去寻找吗？
答案是肯定的，原因就是长度为 1 的所有连续数字中最大的和、长度为 2 的所有连续数字中最大的和、长度为 3 的所有连续数字中最大的和 … 长度为 n 的所有连续数字中最大的和，同样是一个升序数组。
算法的话就是对长度进行二分，寻求满足条件的最小长度。
对于长度为 n 的数组，我们先去判断长度为 n/2 的连续数字中最大的和是否大于等于 s。
- 如果大于等于
s ，那么我们需要减少长度，继续判断所有长度为 n/4 的连续数字
- 如果小于
s，我们需要增加长度，我们继续判断所有长度为 (n/2 + n) / 2，也就是 3n/4 的连续数字。
可以再结合下边的代码看一下。
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
| public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int minLen = 0, maxLen = n;
int midLen;
int min = -1;
while (minLen <= maxLen) {
midLen = (minLen + maxLen) >>> 1;
if (getMaxSum(midLen, nums) >= s) {
maxLen = midLen - 1;
min = midLen;
} else {
minLen = midLen + 1;
}
}
return min == -1 ? 0 : min;
}
private int getMaxSum(int len, int[] nums) {
int n = nums.length;
int sum = 0;
int maxSum = 0;
for (int i = 0; i < len; i++) {
sum += nums[i];
}
maxSum = sum;
for (int i = len; i < n; i++) {
sum += nums[i];
sum = sum - nums[i - len];
maxSum = Math.max(maxSum, sum);
}
return maxSum;
}
|