xiedaxia1hao
commented
3 years ago 滑动窗口的模版
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。 示例: 输入: target = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
题意要求寻找一个连续的子数组，并且子数组的和要大于等于目标值target，这也是一种数组加和的方式。回想到上面的滑动窗口，窗口逐步扩大的时候，可以累加窗口元素的和，如果大于目标s，那么就等于存在一个解。比如[2,3,1,2]这个子数组，是hi不停想右扩展得到的。
但是有解不代表有最优解。假设上面第4个元素就是7，那么[2,3,1,7]自然是一个解，但是单纯的[7]也是一个解。因此我们需要不断的缩小窗口，来找到最小窗口的解。
// Time Complexity: O(n)
// Space Complexity: O(1)
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int minLen = Integer.MAX_VALUE, lo = 0, sum = 0;
for(int hi = 0; hi < nums.length; hi++) {
sum += nums[hi];
while(sum >= target) {
minLen = Math.min(minLen, hi-lo+1);
sum -= nums[lo++];
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
}和第一题一样，初始化窗口为 0，然后 hi 向右移动。每移动一格窗口后，检测当前的窗口计数器是否有解，有解即记录更新解，并且缩小窗口。
一般求最小子数组，有可能没解，因此我们可以把初始化解设为数组本身长度+1或者Integer.MAX_VALUE，方便最后我们判断是否有解的情况。
从上面的两个题大致可以看出，滑动窗口的套路无怪乎两步：
- 向右滑动一格，
- 滑动之后检测窗口计数器和题意要求，适当的缩小窗口
伪代码如下：
lo = 0, hi = 0;
for(int hi = 0; hi < nums.length; hi++) {
windows.add(nums[hi])
while(is_valid) {
handle(res)
windows.remove(s[lo++])
}
}
leetcode的643. 子数组最大平均数 I
借助上面的题目可以一窥滑动窗口套路。滑动窗口的本质是窗口扩大的过程中，寻找一个解，然后窗口缩小的时候寻找一个最优解。