图解：滑动窗口算法模板（Java语言）
·
刷了十几道双指针的题，每次遇到新题还是懵？上一篇讲了「对撞指针」和「快慢指针」，这篇把三兄弟的最后一个——滑动窗口彻底讲透。
📖 目录
一、滑动窗口到底是什么？
先一句话总结：
滑动窗口 = 用两个同向指针维护一个「窗口」，通过右指针扩张、左指针收缩来高效解决问题。
和其他两种双指针对比一下：
┌────────────────────────────────────────────────────────┐
│ 双指针三兄弟对比 │
├──────────┬──────────────┬───────────────────────────────┤
│ 形态 │ 指针方向 │ 典型场景 │
├──────────┼──────────────┼───────────────────────────────┤
│ 对撞指针 │ ← → 相向而行 │ 有序数组、回文判断 │
│ 快慢指针 │ → → 同向而行 │ 链表环检测、去重 │
│ 滑动窗口 │ → → 同向夹逼 │ 最长子串/子数组、覆盖问题 │
└──────────┴──────────────┴───────────────────────────────┘
滑动窗口的精髓在于：
- 右指针（right）：不断向右扩大窗口，把新元素纳入考虑
- 左指针（left）：当窗口不满足条件时，向右收缩，剔除无用元素
- 窗口内的内容：就是当前考虑的「子串/子数组」
二、核心原理：右扩左缩
用一个具体例子来感受。给定字符串 "abcabcbb"，求无重复字符的最长子串：
初始状态：窗口为空
right = -1, left = 0
第1步：right 右移，加入 'a'
a b c a b c b b
^ ^
L R
窗口 = [a] 无重复 ✅
第2步：right 右移，加入 'b'
a b c a b c b b
^ ^
L R
窗口 = [a,b] 无重复 ✅
第3步：right 右移，加入 'c'
a b c a b c b b
^ ^
L R
窗口 = [a,b,c] 无重复 ✅
第4步：right 右移，加入 'a'—— 重复了！❌
a b c a b c b b
^ ^
L R
窗口 = [a,b,c,a] 'a' 重复！
第5步：left 右移，直到窗口无重复
a b c a b c b b
^ ^
L R
窗口 = [b,c,a] 无重复 ✅
（left 从 0 移到 1）
... 继续这个过程 ...
核心逻辑就一句话：
right 一直右移扩大窗口，发现不满足条件了，就移动 left 收缩窗口，直到重新满足条件。
因为每个元素最多被 left 和 right 各访问一次，所以时间复杂度是 O(n)。
三、通用模板代码
所有滑动窗口的题目，代码结构几乎都长这样：
public int slidingWindow(String s) {
// 1. 用什么数据结构维护窗口状态？
// 常见选择：HashMap（字符计数）、Set（去重）、int[]（字符频次）
Map<Character, Integer> window = new HashMap<>();
int left = 0; // 窗口左边界
int result = 0; // 记录最优结果
for (int right = 0; right < s.length(); right++) {
// 2. 右指针右移：将新元素加入窗口
char c = s.charAt(right);
window.put(c, window.getOrDefault(c, 0) + 1);
// 3. 检查窗口是否满足条件？
// 如果【不满足】，就移动 left 收缩窗口
while (窗口不满足条件) {
char d = s.charAt(left);
window.put(d, window.get(d) - 1);
if (window.get(d) == 0) {
window.remove(d);
}
left++; // 左指针右移，窗口缩小
}
// 4. 窗口满足条件了，更新最优结果
result = Math.max(result, right - left + 1);
}
return result;
}
模板四步走：
┌─────────────────────────────────────────────────┐
│ ① 初始化：left=0，窗口数据结构 │
│ ② 右扩：right 每轮右移一步，新元素加入窗口 │
│ ③ 左缩：检查条件，不满足则 left 右移（while循环） │
│ ④ 更新：窗口满足条件时，更新最优解 │
└─────────────────────────────────────────────────┘
不同题目的区别只在于：
- 窗口用什么数据结构（Map / Set / int[]）
- 什么条件触发 left 收缩（while 的判断条件）
- 更新什么结果（最大值、最小值、计数等）
四、经典题1：无重复字符的最长子串
LeetCode 3 — 无重复字符的最长子串
给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。
4.1 思路分析
- 用 Set 维护窗口内的字符
- right 每加入一个新字符，检查 Set 里有没有
- 如果重复了：left 不断右移，把左边的字符从 Set 中移除，直到窗口里没有重复
4.2 图解过程
以 "pwwkew" 为例：
Step 1: right=0, 加入 'p'
p w w k e w
^
L R
Set = {p} 无重复 ✅ maxLen = 1
Step 2: right=1, 加入 'w'
p w w k e w
^ ^
L R
Set = {p,w} 无重复 ✅ maxLen = 2
Step 3: right=2, 加入 'w'—— 重复！
p w w k e w
^ ^
L R
Set = {p,w,w} 'w' 重复 ❌
→ left 右移，移除 'p'
Set = {w,w} 还重复 ❌
→ left 右移，移除 'w'
Set = {w} 无重复 ✅
p w w k e w
^
L R
maxLen = 2（不变）
Step 4: right=3, 加入 'k'
p w w k e w
^ ^
L R
Set = {w,k} 无重复 ✅ maxLen = 2
Step 5: right=4, 加入 'e'
p w w k e w
^ ^
L R
Set = {w,k,e} 无重复 ✅ maxLen = 3
Step 6: right=5, 加入 'w'—— 重复！
p w w k e w
^ ^
L R
Set = {w,k,e,w} 'w' 重复 ❌
→ left 右移，移除 'w'
Set = {k,e,w} 无重复 ✅
p w w k e w
^ ^
L R
maxLen = 3
4.3 完整代码
class Solution {
public int lengthOfLongestSubstring(String s) {
// 用 Set 维护窗口内的字符（保证无重复）
Set<Character> window = new HashSet<>();
int left = 0; // 窗口左边界
int maxLen = 0; // 记录最长长度
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果当前字符在窗口中已存在 → 收缩左边界
while (window.contains(c)) {
window.remove(s.charAt(left));
left++;
}
// 加入当前字符
window.add(c);
// 更新最长长度
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}
4.4 复杂度分析
| 复杂度 | 值 | 说明 |
|---|---|---|
| 时间 | O(n) | 每个字符最多被 left 和 right 各访问一次 |
| 空间 | O(min(m,n)) | m 为字符集大小，n 为字符串长度，取较小值 |
五、经典题2：最小覆盖子串
LeetCode 76 — 最小覆盖子串
给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。
5.1 思路分析
这道题比上道难一点，因为：
- 需要统计字符频率（t 中可能有重复字符）
- 窗口需要包含 t 的所有字符（不仅仅是"无重复"）
- 求最小窗口（不是最大）
核心思路：
- 用 Map 记录 t 中每个字符的「需要次数」
- right 右移，加入字符并减少「需要次数」
- 当所有字符的「需要次数」都 ≤ 0 时（窗口覆盖了 t），尝试收缩 left
- 记录过程中的最小窗口
5.2 图解过程
以 s = "ADOBECODEBANC", t = "ABC" 为例：
need = {A:1, B:1, C:1} ← 还需要覆盖的字符
Step 1-5: right 不断右移
A D O B E C O D E B A N C
^ ^
L R
窗口 = [A,D,O,B,E,C] 覆盖了 A,B,C ✅
need = {A:0, B:0, C:0}
→ 记录当前窗口长度 = 6
Step 6: 尝试收缩 left
移除 'A' → need[A]=1，不再覆盖 ❌，停止收缩
A D O B E C O D E B A N C
^ ^
L R
窗口 = [D,O,B,E,C] 未覆盖 ❌
... right 继续右移 ...
最终找到最小窗口 = "BANC"（长度4）
A D O B E C O D E B A N C
^ ^
L R
5.3 完整代码
class Solution {
public String minWindow(String s, String t) {
if (s == null || s.length() == 0 || t == null || t.length() == 0) {
return "";
}
// need: 记录 t 中每个字符还需要出现几次
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
// needCnt: 还有多少个字符的「需要次数」> 0
int needCnt = need.size();
int left = 0; // 窗口左边界
int minLen = Integer.MAX_VALUE;
int start = 0; // 最小窗口的起始位置
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 右扩：将字符加入窗口
if (need.containsKey(c)) {
need.put(c, need.get(c) - 1);
// 如果该字符的「需要次数」恰好变为0，说明这个字符已满足
if (need.get(c) == 0) {
needCnt--;
}
}
// 当所有字符都满足时，尝试收缩左边界
while (needCnt == 0) {
// 更新最小窗口
if (right - left + 1 < minLen) {
minLen = right - left + 1;
start = left;
}
// 左缩：移除左边界的字符
char d = s.charAt(left);
if (need.containsKey(d)) {
need.put(d, need.get(d) + 1);
// 如果该字符的「需要次数」变为1，说明不再满足
if (need.get(d) > 0) {
needCnt++;
}
}
left++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
}
5.4 复杂度分析
| 复杂度 | 值 | 说明 |
|---|---|---|
| 时间 | O(m+n) | m= |
| 空间 | O(k) | k 为 t 中不同字符的数量 |
六、经典题3：找到字符串中所有字母异位词
LeetCode 438 — 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的「异位词」的起始索引。
6.1 思路分析
异位词 = 字符种类和数量完全相同，顺序可以不同。
关键观察：如果 p 长度为 m，那异位词就是一个长度固定为 m 的滑动窗口！
和前面的"可变窗口"不同，这题是定长窗口：
- 窗口大小始终等于 p 的长度
- 每次右移一步：去掉最左边的字符，加入右边的新字符
6.2 图解过程
以 s = "cbaebabacd", p = "abc" 为例：
p 的字符频率: {a:1, b:1, c:1}
窗口大小 = 3
Step 1: 窗口 [0,2] = "cba"
c b a e b a b a c d
^ ^ ^
L ? R
窗口频率 = {a:1, b:1, c:1} == p 的频率 ✅
→ ans = [0]
Step 2: 窗口右移 [1,3] = "bae"
c b a e b a b a c d
^ ^ ^
L ? R
窗口频率 = {a:1, b:1, e:1} != p 的频率 ❌
Step 3: 窗口右移 [2,4] = "aeb"
c b a e b a b a c d
^ ^ ^
L ? R
窗口频率 = {a:1, e:1, b:1} != p 的频率 ❌
Step 4: 窗口右移 [3,5] = "eba"
c b a e b a b a c d
^ ^ ^
L ? R
窗口频率 = {e:1, b:1, a:1} != p 的频率 ❌
Step 5: 窗口右移 [4,6] = "bab"
c b a e b a b a c d
^ ^ ^
L ? R
窗口频率 = {b:2, a:1} != p 的频率 ❌
Step 6: 窗口右移 [5,7] = "aba"
c b a e b a b a c d
^ ^ ^
L ? R
窗口频率 = {a:2, b:1} != p 的频率 ❌
Step 7: 窗口右移 [6,8] = "bac"
c b a e b a b a c d
^ ^ ^
L ? R
窗口频率 = {b:1, a:1, c:1} == p 的频率 ✅
→ ans = [0, 6]
最终结果: [0, 6]
6.3 完整代码
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> ans = new ArrayList<>();
if (s.length() < p.length()) {
return ans;
}
int pLen = p.length();
// pCount: p 的字符频率
int[] pCount = new int[26];
for (char c : p.toCharArray()) {
pCount[c - 'a']++;
}
// sCount: 当前窗口的字符频率
int[] sCount = new int[26];
// 初始化第一个窗口
for (int i = 0; i < pLen; i++) {
sCount[s.charAt(i) - 'a']++;
}
// 比较数组是否相等
if (Arrays.equals(pCount, sCount)) {
ans.add(0);
}
// 滑动窗口：每次右移一步
for (int i = pLen; i < s.length(); i++) {
// 去掉最左边的字符
sCount[s.charAt(i - pLen) - 'a']--;
// 加入右边的新字符
sCount[s.charAt(i) - 'a']++;
// 比较频率数组
if (Arrays.equals(pCount, sCount)) {
ans.add(i - pLen + 1);
}
}
return ans;
}
}
6.4 复杂度分析
| 复杂度 | 值 | 说明 |
|---|---|---|
| 时间 | O(n × 26) | n 为 s 长度，每次比较26个字符的数组 |
| 空间 | O(1) | 固定26长度的数组 |
七、三道题对比总结
把三道题放在一起看，发现套路完全一样：
| 对比项 | 无重复最长子串 | 最小覆盖子串 | 字母异位词 |
|---|---|---|---|
| 题目 | LeetCode 3 | LeetCode 76 | LeetCode 438 |
| 窗口类型 | 可变（求最大） | 可变（求最小） | 定长 |
| 数据结构 | Set | HashMap | int[26] |
| left 触发条件 | 字符重复时收缩 | 全部覆盖后尝试收缩 | 定长，每步都移 |
| 优化方向 | 最大长度 | 最小长度 | 计数 |
| 时间 | O(n) | O(m+n) | O(n) |
| 空间 | O(min(m,n)) | O(k) | O(1) |
一句话总结选择策略：
┌─────────────────────────────────────────────────────────┐
│ 看到"子串/子数组" + "最xx" → 想滑动窗口 │
│ │
│ "最长" → 窗口尽可能大 → 满足条件时才更新结果 │
│ "最短" → 窗口尽可能小 → 不满足条件时更新左边界 │
│ "所有" → 定长窗口 → 每步右移，比较窗口内容 │
└─────────────────────────────────────────────────────────┘
记住这个模板，80%的滑动窗口题直接套就行。剩下20%需要微调 while 的判断条件，但框架不变。
💡 刷题建议：先把这三道吃透（每道至少自己手写3遍），再去做 LeetCode 209（长度最小的子数组）、904（水果成篮）、763（划分字母区间），你会发现全是同一套路。
如果觉得有帮助，点赞 + 收藏支持一下！有问题欢迎评论区讨论 💬
更多推荐
9
0- 0
已为社区贡献7条内容
所有评论(0)