image.png
思路
-
sum -= nums[i], i++滑动窗口的精髓在于这行代码
遍历数组向滑动窗口中添加元素累加数值, 并每次判断是否符合条件,
如果 sum < target 则一直累加sum-
sum >= target记录当前窗口的长度, 并更新窗口的最小长度, 因为是求连续的子数组长度, 所以先将窗口最左边的元素移除, 例[3,1,2,4] > target 移除3 剩下[1,2,4] 符合条件 更新最小长度, 如果将最左边元素移除[2,3,1,2]->[3,1,2] 任不符合条件, 窗口就继续向右边移动, 其实也就是重复的1.2步骤, 遍历到数组结束
窗口移动过程如下
[2,3,1,2,4,3]
[2,3,1,2]->[3,1,2]
[3,1,2,4] -> [1,2,4] 长度3
[2,4] ->[2,4,3]
[2,4,3] -> [4,3] 长度2
最终结果是[4,3] 最小长度是2
while (sum >= target) { // 这里如果写if 窗口就没法滑动了应该写while
int subLen = j - i + 1;
minLen = minLen > subLen ? subLen : minLen;
sum -= nums[i];
i++;
}
滑动窗口最优解 O(n)
public static int minSubArrayLen3(int target, int[] nums) {
int minLen = Integer.MAX_VALUE;
int i = 0; // 滑动窗口的起始位置
int sum = 0;
for (int j = 0; j < nums.length ; j++) {
sum += nums[j];
while (sum >= target) { // 这里如果写if 窗口就没法滑动了应该写while
int subLen = j - i + 1; // 计算子数组长度 + 1是因为数组下标从0 开始
minLen = minLen > subLen ? subLen : minLen; // 每次循环更新最小长度
sum -= nums[i]; // 滑动窗口的精髓 更新完毕后 移除到窗口最左边的数值,方便窗口的下个回合的计算
i++; // 窗口左边界也要向左滑动
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
下面是自己想的暴力解法 超时了.
//输入：target = 7, nums = [2,3,1,2,4,3]
public static int minSubArrayLen(int target, int[] nums) {
int minLen = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (sum >= target) {
minLen = minLen > j - i + 1 ? j - i + 1 : minLen;
}
}
}
return minLen;
}
//输入：target = 7, nums = [2,3,1,2,4,3]
public static int minSubArrayLen1(int target, int[] nums) {
int minLen = Integer.MAX_VALUE;
int k = 0;
int sum = 0;
int i = 0;
while (k < nums.length && i < nums.length) {
sum += nums[i];
if (sum >= target) {
int subLen = i - k + 1;
minLen = minLen > subLen ? subLen : minLen;
++k;
i = k;
sum = 0;
continue;
}
i++;
}
return minLen;
}
