【优选算法】滑动窗口 {何时使用滑动窗口？如何使用滑动窗口？如何确定更新结果的时机？滑动窗口是如何提高效率的？相关编程题解析}

一、经验总结

何时使用滑动窗口？
在使用暴力解法解题时，发现可以将其优化为同向双指针，既可以使用滑动窗口。

如何使用滑动窗口？
1. 定义窗口控制变量n，进窗口，判断，出窗口都需要操作窗口控制变量。
2. 定义窗口的左右端点，left = 0, right = 0；
3. 进窗口： ++n;
4. 判断：while(n > k)
5. 出窗口： --n;
6. 在适当的时机更新结果。

如何确定更新结果的时机？
* 可以选择跟随进窗口更新结果（判断外），或跟随出窗口更新结果（判断内）。
* 借助示例模拟滑动窗口算法的执行过程：如果是在出窗口时刚好满足结果的形成条件则跟随出窗口，如果是在出窗口时刚好不满足结果的形成条件则跟随进窗口。

滑动窗口是如何提高效率的？
利用单调性规避了许多没有必要的枚举行为，单趟滑动窗口的时间复杂度O(n)。

---

二、相关编程题

2.1 长度最小的子数组

题目链接：209. 长度最小的子数组

算法原理：

题解：209. 长度最小的子数组（滑动窗口）

最值问题：求最小值应该将变量初始化为最大(INT_MAX)，求最大值应该将变量初始化为最小(0或INT_MIN)。

---

2.2 无重复字符的最长子串

题目链接：3. 无重复字符的最长子串

算法原理：

题解：3. 无重复字符的最长子串（滑动窗口，哈希表）

哈希数组：

1. 如果使用哈希表统计的是普通ascii字符的出现频次，则可以使用一个大小为128的数组充当哈希表，效率更高。
2. 一定要记得将数组初始化为空！

---

2.3 最大连续1的个数 III

题目链接：1004. 最大连续1的个数 III

算法原理：

题解：1004. 最大连续1的个数 III（滑动窗口）

简化题目：将复杂的题目表述化简为简单易于思考的版本。如可以将此题化简为：找出最长的子数组，0的个数不超过k个

---

2.4 将 x 减到 0 的最小操作数

题目链接：1658. 将 x 减到 0 的最小操作数

算法原理：

题解：1658. 将 x 减到 0 的最小操作数（滑动窗口，细节问题）

注意：

1. 正难则反（化简）：可以将此题转化为求元素之和恰好等于sum-x的最长子数组的长度
2. 尽量使出窗口判断更简单。如，可以判断>=也可以判断>，选择判断>，使思路简明清晰。
3. 细节处理：写完代码后要注意极端、特殊情况。

---

2.5 水果成篮

题目链接：904. 水果成篮

算法原理：

题解：904. 水果成篮（滑动窗口）

---

2.6 找到字符串中所有字母异位词

题目链接：438. 找到字符串中所有字母异位词

算法原理：

题解：438. 找到字符串中所有字母异位词（滑动窗口，哈希表）

注意：

1. 固定长度的滑动窗口：窗口长度就是出窗口的判定条件。窗口元素每退出1个就会进入1个，因此出窗口的判断条件使用if语句即可。
2. 优化更新结果的判断条件：原本需要遍历比较hash1和hash2中字母的出现频次，使所有字母的出现次数相同，但这样做效率太低。因此定义cnt统计s子串中有效字符的个数，所谓有效字符即在p字符串中出现的字符。又因为是固定长度的滑动窗口，更新结果时仅需判断cnt == len即可。

---

2.7 串联所有单词的子串

题目链接：30. 串联所有单词的子串

算法原理：

题解：30. 串联所有单词的子串（滑动窗口，哈希表）

---

2.8 最小覆盖子串

题目链接：76. 最小覆盖子串

算法原理：

题解：76. 最小覆盖子串（滑动窗口，哈希表）