夜雨聆风前置知识
阅读本文前，最好先理解两个基础概念：
双指针：用两个索引共同维护一段区间或一种状态。 子数组/子串：要求元素在原数组或字符串中连续。
滑动窗口本质上也是双指针。只不过两个指针通常同向移动：right 负责扩张窗口，left 负责收缩窗口，二者之间的区间就是当前窗口。
全局地图
处理数组、字符串、链表问题时，双指针经常分成几类：
快慢指针：两个指针同向移动，一般用于原地修改、链表环、窗口维护。 左右指针：两个指针相向而行或相背而行，一般用于有序数组、反转、回文。 滑动窗口：快慢指针的变体，用 [left, right)维护一个连续区间。
滑动窗口主要解决这类问题：
找满足条件的最短子串 找满足条件的最长子串 判断某个排列是否出现在字符串中 找出所有满足条件的起点
只要题目关键词里出现“连续子数组”“连续子串”“最长”“最短”“包含”“不重复”，就可以先想一想能不能用滑动窗口。
滑动窗口框架概览
如果用暴力解法枚举所有子数组，通常需要两层循环：
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
// nums[i..j] 是一个子数组
}
}
这种写法会枚举所有起点和终点，时间复杂度通常是 O(N²)。
滑动窗口的做法是维护一个窗口，不断向右移动窗口边界，并在移动过程中更新答案：
// 索引区间 [left, right) 是窗口
int left = 0, right = 0;
while (right < nums.length) {
// 增大窗口
window.add(nums[right]);
right++;
while (窗口需要收缩) {
// 缩小窗口
window.remove(nums[left]);
left++;
}
}
核心思想：right 负责把新元素纳入窗口，left 负责在窗口不再合适时丢掉旧元素。窗口里的统计信息始终跟着两个指针增量更新。
为啥是 O(N)？
滑动窗口代码里虽然有嵌套 while，但时间复杂度不是 O(N²)。
原因是 left 和 right 都只会向右移动，不会回退。每个元素最多进入窗口一次，再离开窗口一次，所以总操作次数和输入长度成正比，整体复杂度是 O(N)。
暴力解法的问题在于内层指针会反复从不同起点开始扫描，同一个元素可能被重复计算很多次。
为啥滑动窗口不是穷举所有子数组？
滑动窗口并没有穷举所有子数组。要完整枚举所有子数组，两层循环是绕不开的。
滑动窗口能提速，是因为很多题目不需要看完所有区间。只要窗口状态满足某些条件，就可以确定一批区间已经没有继续枚举的必要，于是移动左指针完成剪枝。
所以滑动窗口解决的不是“如何枚举所有子串”，而是“如何在必要状态足够的情况下，跳过明显无效的区间”。
滑动窗口算法伪码框架
下面是通用模板。本文例题大多是字符串问题，所以输入写成字符串；如果题目是数组，把字符替换成数组元素即可。
defsliding_window(s: str):
# 根据题目选择合适的数据结构维护窗口状态
# 统计字符次数可以用 dict
# 统计窗口和可以用 int
window = {}
left = 0
right = 0
while right < len(s):
# c 是将移入窗口的字符
c = s[right]
right += 1
# 更新窗口数据
# ...
# 调试窗口范围，提交时不要保留 print
# print(f"window: [{left}, {right})")
# 判断左侧窗口是否需要收缩
while left < right and need_shrink(window):
# d 是将移出窗口的字符
d = s[left]
left += 1
# 更新窗口数据
# ...
使用这个模板时，重点回答三个问题：
什么时候扩大窗口？新元素进入窗口后，要更新哪些数据？ 什么时候缩小窗口？旧元素离开窗口后，要更新哪些数据？ 什么时候更新答案？
后面的四道题，本质上都是在回答这三个问题。
一、最小覆盖子串
力扣第 76 题：最小覆盖子串，难度 Hard。
题目要求：给定字符串 s 和 t，返回 s 中涵盖 t 所有字符的最小子串。如果不存在，返回空字符串。
示例：
输入: s = "ADOBECODEBANC", t = "ABC"
输出: "BANC"
解释: "BANC" 包含 A、B、C，且长度最短。
注意，t 中可能有重复字符，所以窗口里对应字符的数量也必须足够。
思路
如果暴力枚举，可以写成：
for i in range(len(s)):
for j in range(i + 1, len(s) + 1):
if s[i:j] 包含 t 的所有字符:
更新答案
这个思路直接，但复杂度太高。
滑动窗口的做法是：
用 [left, right)表示当前窗口。不断移动 right扩大窗口，直到窗口覆盖t。窗口满足要求后，移动 left缩小窗口，并持续更新最短答案。重复上述过程，直到 right到达字符串末尾。
这里用两个哈希表维护计数：
need：t中每个字符需要出现几次。window：当前窗口中相关字符出现几次。
再用 valid 表示已经有多少种字符满足了 need 的数量要求。当 valid == len(need) 时，说明当前窗口已经覆盖了 t。
为什么窗口用左闭右开？
[left, right) 的好处是边界清楚。
初始时 [0, 0) 是空窗口；当 right 右移后，窗口自然包含新加入的元素。这样扩大和缩小窗口时，代码不容易出现边界错误。
代码
classSolution:
defminWindow(self, s: str, t: str) -> str:
need, window = {}, {}
for c in t:
need[c] = need.get(c, 0) + 1
left = 0
right = 0
valid = 0
# 记录最小覆盖子串的起始索引及长度
start = 0
length = float("inf")
while right < len(s):
# c 是将移入窗口的字符
c = s[right]
right += 1
# 更新窗口数据
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
valid += 1
# 窗口已覆盖 t，开始收缩
while valid == len(need):
# 在这里更新最小覆盖子串
if right - left < length:
start = left
length = right - left
# d 是将移出窗口的字符
d = s[left]
left += 1
# 更新窗口数据
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
return""if length == float("inf") else s[start:start + length]
关键细节：
字符进入窗口时，增加 window[c]。如果 window[c] == need[c]，说明这个字符已经满足要求，valid += 1。当 valid == len(need)时，窗口是可行解。本题要找最短可行窗口，所以答案应该在收缩窗口时更新。
如果使用 Java，比较 Integer、String 等包装类型时应使用 equals，不要直接用 == 判断值相等。
二、字符串排列
力扣第 567 题：字符串的排列，难度 Medium。
题目要求：给定两个字符串 s1 和 s2，判断 s2 是否包含 s1 的某个排列。
示例：
输入: s1 = "ab", s2 = "eidbaooo"
输出: true
解释: s2 包含 s1 的排列之一 "ba"。
思路
排列要求字符种类和字符数量完全一致，所以这道题可以理解成：
在 s2 中找一个长度等于 len(s1) 的子串，并且这个子串包含 s1 的所有字符。
这就是一个定长滑动窗口问题。窗口长度达到 len(s1) 时，就判断当前窗口是否合法，然后向右滑动。
代码
classSolution:
# 判断 s 中是否存在 t 的排列
defcheckInclusion(self, t: str, s: str) -> bool:
need = {}
window = {}
for c in t:
need[c] = need.get(c, 0) + 1
left = 0
right = 0
valid = 0
while right < len(s):
c = s[right]
right += 1
# 更新窗口数据
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
valid += 1
# 窗口长度达到 t 的长度，开始判断并收缩
while right - left >= len(t):
if valid == len(need):
returnTrue
d = s[left]
left += 1
# 更新窗口数据
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
returnFalse
和最小覆盖子串相比，这道题主要改了两个地方：
收缩窗口的时机变成 right - left >= len(t)，因为排列长度必须固定。一旦 valid == len(need)，说明找到了合法排列，直接返回True。
小优化
因为这里维护的是定长窗口，每次最多只需要移出一个字符，所以内层 while 也可以改成 if。保留 while 的好处是和通用模板保持一致。
三、找所有字母异位词
力扣第 438 题：找到字符串中所有字母异位词，难度 Medium。
题目要求：给定两个字符串 s 和 p，找到 s 中所有 p 的异位词子串，返回这些子串的起始索引。
示例：
输入: s = "cbaebabacd", p = "abc"
输出: [0, 6]
解释: "cba" 和 "bac" 都是 "abc" 的异位词。
思路
异位词本质上就是排列。所以这题和上一题几乎一样：
上一题是判断是否存在一个合法窗口。 这题是收集所有合法窗口的起始位置。
窗口仍然是定长窗口，长度为 len(p)。
代码
classSolution:
deffindAnagrams(self, s: str, t: str) -> list[int]:
need = {}
window = {}
for c in t:
need[c] = need.get(c, 0) + 1
left = 0
right = 0
valid = 0
res = []
while right < len(s):
c = s[right]
right += 1
# 更新窗口数据
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
valid += 1
# 窗口长度达到 t 的长度，开始判断并收缩
while right - left >= len(t):
if valid == len(need):
res.append(left)
d = s[left]
left += 1
# 更新窗口数据
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
return res
关键细节：
判断条件仍然是 valid == len(need)。不同的是找到合法窗口后，不是返回，而是把 left加入结果数组。
四、最长无重复子串
力扣第 3 题：无重复字符的最长子串，难度 Medium。
题目要求：给定字符串 s，找出其中不含重复字符的最长子串长度。
示例：
输入: s = "abcabcbb"
输出: 3
解释: 最长无重复子串是 "abc"。
思路
这道题不需要 need 和 valid，只需要维护窗口里每个字符出现的次数。
当新加入的字符 c 导致 window[c] > 1 时，说明窗口里出现了重复字符。此时移动 left 收缩窗口，直到这个重复字符只出现一次。
代码
classSolution:
deflengthOfLongestSubstring(self, s: str) -> int:
window = {}
left = 0
right = 0
res = 0
while right < len(s):
c = s[right]
right += 1
# 更新窗口数据
window[c] = window.get(c, 0) + 1
# 如果窗口中存在重复字符，就收缩窗口
while window[c] > 1:
d = s[left]
left += 1
window[d] = window.get(d, 0) - 1
# 收缩完成后，窗口一定没有重复字符
res = max(res, right - left)
return res
这道题要注意答案更新的位置。
前面几道题是在找到可行窗口时更新或判断答案；这道题要等窗口收缩完成后再更新 res，因为只有这时窗口才保证没有重复字符。
总结
valid == len(need) | |||
right - left >= len(t)valid == len(need) | |||
right - left >= len(t)valid == len(need) | left | ||
window[c] > 1 |
决策路径：
遇到「最短覆盖」→ 扩大到满足条件，再收缩并更新答案。 遇到「排列 / 异位词」→ 使用定长窗口，长度达到目标后判断是否合法。 遇到「最长无重复」→ 出现重复就收缩，窗口合法后更新最大值。 遇到「子数组 / 子串 + 条件约束」→ 先尝试定义窗口状态，再判断 left和right的移动规则。
最后回到滑动窗口的三个核心问题：
什么时候扩大窗口？ 什么时候缩小窗口？ 什么时候更新答案？
把这三个问题想清楚，滑动窗口题目基本就能稳定套出代码。
