一、滑窗思想
滑动窗口，简称滑窗，是快慢指针的一种应用技巧，两个指针之间形成一个窗口，右指针不断扩张，左指针按条件收缩，随着窗口的扩大和缩小找到满足条件的答案。
滑窗分为 2 种：
静态窗口：窗口中的元素个数不变；
动态窗口：窗口中的元素个数随条件变化。
二、适用场景
滑动窗口适用于：查找满足一定条件的最长或最短子数组、子字符串。
三、滑窗使用思路
3.1 查找最长
-- 左右双指针（L, R）在起始点，R 向右逐位滑动
---- 每次滑动过程中
如果窗口内元素满足条件，R 增加，扩大窗口，并更新最优结果
如果窗口内元素不满足条件，L 增加，缩小窗口
-- R 到达结尾
3.2 查找最短
-- 左右双指针（L, R）在起始点，R 向右逐位滑动
---- 每次滑动过程中
如果窗口内元素不满足条件，R 增加，扩大窗口
如果窗口内元素满足条件，L 增加，缩小窗口，并更新最优结果
-- R 到达结尾
3.3 两个重要问题
1. 什么时候扩大窗口，什么时候收缩窗口？
2. 在扩大窗口还是收缩窗口时更新结果？
-- 获取最长的时候，满足条件扩大窗口、更新结果，不满足条件收缩窗口；
-- 获取最短的时候，满足条件收缩窗口、更新结果，不满足条件扩大窗口。
四、代码框架
int left = 0, right = 0;
while (right < size()) {
// 移入窗口的元素
window.add(s[right]);
// 窗口增大
right++;
// 如果窗口需要收缩
while (left < right && window needs shrink) {
// 移出窗口的元素
window.remove(s[left]);
// 缩小窗口
left++;
}
}
五、练习题目
LeetCode 209. 长度最小的子数组
LeetCode 76. 最小覆盖子串
LeetCode 3. 无重复字符的最长子串