滑动窗口算法在不同场景下的解题模板

目录

一、什么情况下需要用滑动窗口？

二、滑动窗口适合解决什么问题？

三、滑动窗口的核心思想

四、滑动窗口常见分类

类型一：最长无重复窗口

类型二：固定长度窗口

类型三：最短覆盖窗口

类型四：替换连续区间，使整体满足条件

五、四道题的本质区别

六、滑动窗口通用模板一：最长窗口模板

对应 LC3

七、滑动窗口通用模板二：固定长度窗口模板

对应 LC438

八、滑动窗口通用模板三：最短覆盖窗口模板

对应 LC76

九、滑动窗口通用模板四：替换区间 / 窗口外合法模板

对应完美走位

十、四种模板的核心区别

1. 最长窗口

2. 固定长度窗口

3. 最短覆盖窗口

4. 替换区间窗口

十一、滑动窗口解题时如何判断 left 什么时候动？

LC3：窗口出现重复时动 left

LC438：窗口长度超过 p.length 时动 left

LC76：窗口已经满足覆盖条件时动 left

完美走位：窗口外已经合法时动 left

十二、滑动窗口解题时如何判断 right 什么时候动？

十三、滑动窗口中常见变量含义

1. left

2. right

写法一：闭区间 [left, right]

写法二：左闭右开 [left, right)

3. need

4. window

5. valid

6. ans / maxLen / minLen

十四、什么时候用 Map？什么时候用数组？

1. 用数组

2. 用 Map

3. 用普通对象

十五、解滑动窗口题的标准思考步骤

第一步：判断是不是连续区间问题

第二步：判断求最长、最短还是固定长度

第三步：明确窗口表示什么

第四步：明确窗口状态怎么维护

第五步：明确什么时候移动 right

第六步：明确什么时候移动 left

第七步：明确什么时候更新答案

十六、四道题的模板归纳

1. LC3：最长无重复子串模板

2. LC438：固定长度异位词模板

3. LC76：最小覆盖子串模板

4. 完美走位：替换窗口模板

十七、滑动窗口的核心代码骨架

1. 最长合法窗口

2. 最短满足窗口

3. 固定长度窗口

十八、解滑动窗口题需要具备哪些知识储备？

1. 双指针思想

2. 哈希表 / Map

3. 字符频次数组

4. 窗口区间长度计算

闭区间 [left, right]

左闭右开 [left, right)

5. 频次满足条件的判断

6. 复杂度分析

十九、滑动窗口解题口诀

二十、最终总结

一、什么情况下需要用滑动窗口？

一般题目中出现下面这些关键词，就要优先考虑滑动窗口：

连续子串 连续子数组 最长 最短 包含 不包含 满足某种条件 至多 / 至少 固定长度 替换一段连续区间

尤其是这几类问题：

1. 找最长连续子串 / 子数组 2. 找最短连续子串 / 子数组 3. 找固定长度窗口内是否满足条件 4. 找包含目标字符的最短区间 5. 找通过替换一段连续区间使整体满足条件