滑动窗口（Sliding Window）
通过左右指针维护一个窗口区间，在 O(N) 时间内解决子数组/子串问题的算法技巧。
定义
滑动窗口是一种基于快慢双指针的算法技巧，通过维护一个 [left, right) 左闭右开的窗口区间，不断滑动窗口来寻找满足特定条件的最优子数组或子串。它将暴力解法的 O(N²) 时间复杂度优化为 O(N)。
核心特性
| 特性 | 说明 |
|---|---|
| 本质 | 快慢双指针，一快一慢前后相随，中间部分即窗口 |
| 时间复杂度 | O(N)，每个元素进出窗口各一次 |
| 空间复杂度 | O(k)，k 为窗口内不同元素的数量 |
| 适用问题 | 寻找满足某条件的最长/最短子数组（子串） |
| 区间定义 | 左闭右开 [left, right)，便于边界处理 |
基本原理
滑动窗口算法的核心逻辑：
// 索引区间 [left, right) 是窗口
int left = 0, right = 0;
while (right < nums.size()) {
// 增大窗口
window.addLast(nums[right]);
right++;
while (window needs shrink) {
// 缩小窗口
window.removeFirst(nums[left]);
left++;
}
}
执行流程：
- 扩大窗口：移动
right指针，将元素加入窗口，直到窗口满足条件（寻找可行解） - 缩小窗口：移动
left指针，移出窗口元素，优化结果（优化可行解） - 重复：直到
right到达尽头
为什么是 O(N)？
left和right指针只增不减，不回退- 每个元素最多进入窗口一次、离开窗口一次
- 嵌套 while 循环的总执行次数与 N 成正比（均摊分析）
使用框架的三个关键问题
遇到子数组/子串问题，只需回答：
- 什么时候应该移动
right扩大窗口？窗口加入元素时，应该更新哪些数据？ - 什么时候窗口应该暂停扩大，开始移动
left缩小窗口？从窗口移出元素时，应该更新哪些数据？ - 什么时候应该更新结果？在扩大窗口时还是缩小窗口时？
常见类型/变体
1. 最小覆盖子串（LeetCode 76）
问题：在字符串 S 中找到包含 T 所有字符的最短子串。
要点：
- 使用
need哈希表记录 T 中字符需求 - 使用
window哈希表记录窗口中字符计数 - 使用
valid计数器跟踪满足条件的字符数 - 在缩小窗口时更新最优解
2. 字符串排列 / 字母异位词（LeetCode 567, 438）
问题：判断 S 中是否存在 T 的排列，或找到所有异位词的起始索引。
要点：
- 定长窗口，窗口大小 = T.length()
- 当
valid == need.size()时，找到合法排列 - 可用 if 替代 while 判断窗口收缩（因为每次只移出一个字符）
3. 最长无重复子串（LeetCode 3）
问题：找到不含重复字符的最长子串长度。
要点：
- 无需
need和valid，只需window记录字符出现次数 - 当
window.get(c) > 1时收缩窗口 - 在收缩完成后更新结果（确保窗口无重复）
关键技巧
1. 左闭右开区间 [left, right)
- 初始化
left = right = 0时窗口为空 right++后窗口包含s[right-1]- 避免两端都开或两端都闭带来的边界处理麻烦
2. valid 计数器优化
int valid = 0;
// 当窗口中某字符计数满足 need 要求时
if (window.get(c).equals(need.get(c))) {
valid++;
}
// 判断窗口是否满足条件
while (valid == need.size()) {
// 收缩窗口
}
3. 窗口数据结构的对称性
扩大窗口和缩小窗口时的数据更新操作是完全对称的：
- 扩大：
window.put(c, window.getOrDefault(c, 0) + 1); - 缩小：
window.put(d, window.get(d) - 1);
时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 滑动窗口框架 | O(N) | 每个元素进出窗口各一次，指针不回退 |
| 暴力解法（嵌套for） | O(N²) | 指针会回退，元素多次进入离开 |
| 窗口内数据更新 | O(1) | 哈希表操作，均摊常数时间 |
经典算法
相关概念
相关实体
- labuladong：算法学习平台，本文作者
- LeetCode：经典题目来源平台
应用场景
- 寻找满足某条件的最长/最短子数组（子串）
- 字符串包含问题（最小覆盖子串）
- 排列/异位词检测（定长窗口）
- 无重复元素子串
- 和 ≥ target 的最短子数组
注意事项
-
Java Integer 比较：必须使用
equals()而非==比较 Integer 对象- 错误：
window.get(c) == need.get(c) - 正确：
window.get(c).equals(need.get(c))
- 错误：
-
窗口区间定义：建议使用左闭右开
[left, right)，简化边界处理 -
更新结果的时机：根据问题类型决定在扩大还是缩小阶段更新
- 最小覆盖类：通常在缩小窗口时更新
- 最长子串类：在收缩完成后更新（确保窗口合法）
-
定长窗口优化：当窗口长度固定时，可用 if 替代 while 判断收缩
总结
滑动窗口算法通过维护左右指针和窗口数据结构，将嵌套循环的 O(N²) 优化为 O(N)。掌握通用框架后，只需回答三个问题（何时扩大、何时缩小、何时更新），即可解决大部分子数组/子串问题。