# 滑动窗口是什么
这一部分我们要和大家分享的内容是「滑动窗口」。翻开《算法（第 4 版）》《算法导论》，都没有看到「滑动窗口」的定义。唯一有点儿沾边的是《算法导论》讲到「滚动哈希」，其实就是固定长度的滑动窗口。
在我看来「滑动窗口」更像是一种 技巧，还不是编程思想，它的应用没有那么广泛，也就是说：使用「滑动窗口」解决的问题很有局限性，并不像分治思想、减治思想、（深度优先、广度优先）遍历、枚举那样具有普遍意义。
提示：如果大家感兴趣，可以在网上搜索「算法思想」「编程思想」，或者平时在做题的过程中，自己思考和总结一些算法思想，相信是比做算法问题更有意义的事情。
知道「滑动窗口」这个名词还是在「力扣」上刷题，刷到了「Sliding Window」标签的问题。
解决这一类问题的特点是：
- 用于解决在 数组 上的问题；
- 使用两个变量，称为左指针、右指针（或者快指针、慢指针）；
- 右指针先向右移动、左指针再向右边移动，交替进行；
- 直到右指针移动到数组的末尾。
下面的动画展示了这样的过程，它像极了一个窗口在数组上滑动，因此称为「滑动窗口」。
# 理解「滑动窗口」需要先理解「暴力解法」
下面这 2 道问题是使用「滑动窗口」解决的基本问题，它们非常重要。
- 「力扣」第 3 题：无重复字符的最长子串（中等）
- 「力扣」第 209 题：长度最小的子数组（中等）
掌握这些问题的方式就是先思考暴力解法，然后再思考如何优化。
「滑动窗口」问题是典型的应用「循环不变量」解决的问题，比较考验我们编码和调试的能力。
滑动窗口与双指针是基于暴力解法的优化，少考虑很多暴力解法要考虑的子问题，将时间复杂度降到线性。解题时需要考虑的细节较多，定义好「循环不变量」是关键。
思想简单，但是代码比较难一次写对；
滑动窗口的思想是：先向右移动右指针、再向右移动左指针，这样左右指针交替执行（ 不回头 ），可以完成一些问题；
滑动窗口是 暴力解法的优化 ，如何 根据目标函数把暴力解法的一系列解排除掉，是使用滑动窗口的前提 ，一定要分析清楚；
下面提供的是一种参考的写法，请不要照搬，应该 先理解滑动窗口的思想（暴力解法的剪枝） ，然后多加练习，掌握编写代码的技巧和细节。
滑动窗口的参考写法（不是模板，请不要原样照搬，仅供参考，理解算法设计思想是更重要的）：
public class Solution {
public String slidingWindow(String s, String t) {
// 起始的时候，都位于 0，同方向移动
int left = 0;
int right = 0;
while (right < sLen) {
if ( 在右移的过程中检测是否满足条件 ) {
// 对状态做修改，好让程序在后面检测到满足条件
}
// 右边界右移 1 格
right++;
while ( 满足条件 ) {
// 走到这里是满足条件的，左边界逐渐逐渐左移，可以取最小值
if ( 在左移的过程中检测是否不满足条件 ) {
// 对状态做修改，好让程序在后面检测到不满足条件
}
// 左边界左移 1 格
left++;
}
// 走到这里是不满足条件的，右边界逐渐右移，可以取最大值
}
return 需要的结果变量;
}
}
重点问题：
| 题号 | 链接 | 题解 |
|---|---|---|
| 3 | 无重复字符的最长子串 (opens new window)（中等） | 文字题解 (opens new window) |
| 76 | 最小覆盖子串 (opens new window)（困难） | 【视频讲解】 |
| 209 | 长度最小的子数组 (opens new window)（中等） | |
| 424 | 替换后的最长重复字符 (opens new window)（中等） | |
| 1493 | 删掉一个元素以后全为 1 的最长子数组 (opens new window)（中等） |
友情提示：第 3 题和第 76 题是必须要会做的基本问题。上面的问题理解透彻了，下面的问题就可以比较轻松地做出来。
说明：
- 第 3 题：先暴力解法，再优化；
- 第 76 题：滑动窗口的典型问题，重点分析为什么可以使用滑动窗口。字符频数数组可以使用哈希表，也可以直接使用数组；使用 距离 的定义加速计算；
- 第 424 题：重点分析为什么可以使用滑动窗口。设计变量
maxCount的含义：在滑动的过程中，出现的字符频数最多的个数；收集结果的判断语句（while (right - left > maxCount + k)）比较难想到。第 424 题同类问题：「力扣」第 1493 题：删掉一个元素以后全为 1 的最长子数组 (opens new window) 。
public class Solution {
// 第 424 题代码：滑动窗口（暴力解法的优化）
public int longestSubarray(int[] nums) {
int len = nums.length;
int left = 0;
int right = 0;
// 连续的 1 的个数
int ones = 0;
// 删除一个元素以后全为 1 的最长的子串的长度
int maxCount = 0;
int res = 0;
while (right < len) {
if (nums[right] == 1) {
ones++;
}
maxCount = Math.max(maxCount, ones);
right++;
// maxCount + 1 里的 1 就表示删除的那个元素
while (right - left > maxCount + 1) {
if (nums[left] == 1) {
ones--;
}
left++;
}
res = Math.max(res, right - left);
}
// 注意：这里返回 res 要减 1
return res - 1;
}
}
练习：
| 题号 | 题目 | 题解 | 知识点 |
|---|---|---|---|
| 438 | 找到字符串中所有字母异位词 (opens new window)（中等） | ||
| 567 | 字符串的排列 (opens new window)（中等） | ||
| 643 | 子数组最大平均数 I (opens new window)（简单） | ||
| 978 | 最长湍流子数组 (opens new window)（中等） | ||
| 992 | K 个不同整数的子数组 (opens new window)（困难） |
说明：
第 209 题：题目中给出的关键信息：数组里的元素全部是正整数。一共有以下 3 种方法。
方法一：暴力解法
方法二：滑动窗口（分析可以使用滑动窗口的原因）
方法三：构造前缀和数组，然后使用二分查找
第 438 题：同第 76 题；
第 567 题：同第 76 题，收集符合条件的语句不一样而已。
# 入门问题
这些问题用于入门「滑动窗口」问题，通过解决它们理解「滑动窗口」算法是暴力解法的优化。
- 「力扣」第 3 题：无重复字符的最长子串（中等）
- 「力扣」第 209 题：长度最小的子数组（中等）
# 经典问题
这两道经典的「滑动窗口」问题问题包含了一些解决同类问题的技巧。可以把「力扣」第 76 题和第 424 题当作例题学习，然后完成对应的练习。
「力扣」第 76 题和第 424 题在「力扣」的官方题解都有视频题解，都是我讲的，准备了很长时间，相信会对大家有所帮助。
「力扣」第 76 题：最小覆盖子串（困难）
- 练习 1：「力扣」第 438 题：找到字符串中所有字母异位词（中等）
- 练习 2：「力扣」第 567 题：字符串的排列（中等）
- 练习 3：「力扣」第 30 题：串联所有单词的子串（困难）
- 练习 4：「力扣」第 395 题：至少有 K 个重复字符的最长子串（中等）
- 练习 5：「力扣」第 632 题：最小区间（困难）
「力扣」第 424 题：替换后的最长重复字符（中等）
- 练习 1：「力扣」第 1004 题：最大连续 1 的个数 III（中等）
- 练习 2：「力扣」第 1208 题：尽可能使字符串相等（中等）
- 练习 3：「力扣」第 1493 题：删掉一个元素以后全为 1 的最长子数组（中等）
# 其它练习
有了以上的解决问题的经验，下面的这些问题大家可以独立完成了。
- 「力扣」第 713 题：乘积小于 K 的子数组（中等）
- 「力扣」第 1838 题：最高频元素的频数（中等）
- 「力扣」第 1839 题：所有元音按顺序排布的最长子字符串（中等）
- 「力扣」第 904 题：水果成篮（中等）
- 「力扣」第 992 题：K 个不同整数的子数组（困难）
- 「力扣」第 995 题：K 连续位的最小翻转次数（困难）
# 固定长度的滑动窗口问题
这些问题比较简单，大家可以尝试做一下。
- 「力扣」第 643 题：子数组最大平均数 I（简单）
- 「力扣」第 1052 题：爱生气的书店老板（中等）
- 「力扣」第 1423 题：可获得的最大点数（中等）
- 「力扣」第 1456 题：定长子串中元音的最大数目（中等）
- 「力扣」第 1658 题：将 x 减到 0 的最小操作数（中等）
# 名字叫做滑动窗口的问题（需要使用数据结构）
这些问题需要用到一些数据结构，以掌握滑动窗口的性质，可以把它们当作例题学习。
- 「力扣」第 220 题：存在重复元素 III（中等）
- 「力扣」第 239 题：滑动窗口最大值（困难）
- 「力扣」第 480 题：滑动窗口中位数（困难）
- 「力扣」第 1438 题：绝对差不超过限制的最长连续子数组（中等）
作者：liweiwei1419 链接：https://suanfa8.com/sliding-window 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。