滑动窗口算法框架
raw/articles/2026/05/滑动窗口框架.md
一句话总结
提供滑动窗口算法的通用代码框架，通过左右指针维护窗口，将子数组/子串问题的时间复杂度从 O(N²) 优化到 O(N)。
核心要点
1. 滑动窗口基本原理
滑动窗口是快慢双指针的应用，维护一个 [left, right) 左闭右开区间作为窗口，通过扩大和缩小窗口寻找满足条件的最优解。
核心思路：
- 第1步：移动
right扩大窗口，直到满足条件（寻找可行解） - 第2步：移动
left缩小窗口，优化结果（优化可行解） - 重复上述过程，直到
right到达尽头
时间复杂度 O(N) 的原因：
left和right指针只增不减，不回退- 每个元素只进入窗口一次，离开窗口一次
- 嵌套 while 循环的总执行次数与 N 成正比（均摊分析）
2. 通用代码框架
// 滑动窗口算法伪码框架
void slidingWindow(String s) {
// 用合适的数据结构记录窗口中的数据
// 例如：Map 记录字符出现次数，或 int 记录元素和
Object window = ...;
int left = 0, right = 0;
while (right < s.length()) {
// c 是将移入窗口的字符
char c = s[right];
window.add(c);
// 增大窗口
right++;
// 进行窗口内数据的一系列更新
...
// 判断左侧窗口是否要收缩
while (left < right && window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
window.remove(d);
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
3. 使用框架的三个关键问题
遇到子串/子数组问题，只需回答：
- 何时扩大窗口？窗口加入元素时，应该更新哪些数据？
- 何时缩小窗口？移出元素时，应该更新哪些数据？
- 何时更新结果？在扩大阶段还是缩小阶段更新？
4. 四道经典题目
| LeetCode | 力扣 | 难度 | 核心考点 |
|---|---|---|---|
| 76. Minimum Window Substring | 76. 最小覆盖子串 | Hard | 在收缩窗口时更新最短结果 |
| 567. Permutation in String | 567. 字符串的排列 | Medium | 定长窗口，窗口大小 = t.length() |
| 438. Find All Anagrams in a String | 438. 找到字符串中所有字母异位词 | Medium | 定长窗口，收集所有合法起始索引 |
| 3. Longest Substring Without Repeating Characters | 3. 无重复字符的最长子串 | Medium | 无需 need 和 valid，直接检测重复 |
时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 滑动窗口框架 | O(N) | 每个元素进出窗口各一次，指针不回退 |
| 暴力解法（嵌套for） | O(N²) | 指针会回退，元素多次进入离开 |
代码实现
最小覆盖子串（LeetCode 76）
class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
// 记录最小覆盖子串的起始索引及长度
int start = 0, len = Integer.MAX_VALUE;
while (right < s.length()) {
// c 是将移入窗口的字符
char c = s.charAt(right);
// 扩大窗口
right++;
// 进行窗口内数据的一系列更新
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c)))
valid++;
}
// 判断左侧窗口是否要收缩
while (valid == need.size()) {
// 在这里更新最小覆盖子串
if (right - left < len) {
start = left;
len = right - left;
}
// d 是将移出窗口的字符
char d = s.charAt(left);
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d)))
valid--;
window.put(d, window.get(d) - 1);
}
}
}
// 返回最小覆盖子串
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
}
最长无重复子串（LeetCode 3）
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int res = 0;
while (right < s.length()) {
char c = s.charAt(right);
right++;
// 进行窗口内数据的一系列更新
window.put(c, window.getOrDefault(c, 0) + 1);
// 判断左侧窗口是否要收缩
while (window.get(c) > 1) {
char d = s.charAt(left);
left++;
// 进行窗口内数据的一系列更新
window.put(d, window.get(d) - 1);
}
// 在这里更新答案（收缩完成后窗口无重复）
res = Math.max(res, right - left);
}
return res;
}
}
关键技巧
1. 左闭右开区间 [left, right)
- 初始化
left = right = 0时窗口为空 right++后窗口包含s[0]- 避免两端都开或两端都闭带来的边界处理麻烦
2. valid 计数器技巧
- 用于判断窗口是否已满足所有条件
valid == need.size()时说明窗口已覆盖目标字符集- 避免每次都遍历 window 和 need 进行比较
3. Java Integer 比较注意事项
- 必须使用
equals()方法而非==比较 Integer - 错误：
window.get(c) == need.get(c) - 正确：
window.get(c).equals(need.get(c))
应用场景
- 寻找满足某条件的最长/最短子数组（子串）
- 字符串包含问题（最小覆盖子串）
- 排列/异位词检测（定长窗口）
- 无重复元素子串
相关概念
相关实体
- labuladong：算法学习平台作者
- LeetCode：在线算法题库平台
总结
滑动窗口算法通过维护左右指针和窗口数据结构，将嵌套循环的 O(N²) 优化为 O(N)。核心是回答三个问题：何时扩大、何时缩小、何时更新结果。掌握通用框架后，大部分子数组/子串问题都可迎刃而解。