长度最小的子数组
力扣题号209
题目描述
1
2
3
4
5
6
7
8
9
10
11
12
| 给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
|
暴力循环
首先还是最简单暴力的 双重循环for循环遍历，记录长度然后对比取最小值
循环大法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int minSubArrayLen(int target, int[] nums) {
int result = Integer.MAX_VALUE;
int subLen = 0;
int sum = 0;
for (int j = 0; j < nums.length; j++) {
sum = 0;
for (int i = j; i < nums.length; i++) {
sum = sum + nums[i];
if (sum >= target ){
subLen = i - j + 1;
result = subLen < result ? subLen : result;
break;
}
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
|
滑动窗口
首先上面的暴力循环是过不去力扣的编译的哈哈哈哈，因为时间超限制了，所以还得是滑动窗口。所谓的滑动窗口也算是双指针的一种，不断调节两个指针之间的间距，也就是不断地调节子数组的其实位置和终止位置，从而得到最小的子数组
滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int minSubArrayLen(int target, int[] nums) {
int result = Integer.MAX_VALUE;
int i = 0;
int subLen;
int sum = 0;
for (int j = 0; j < nums.length; j++) {
sum = sum + nums[j];
while (sum >= target) {
subLen = j - i + 1;
result = Math.min(subLen, result);
sum = sum - nums[i++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
|
