滑动窗口：基本思路与四道 LeetCode 经典题
1. 滑动窗口的基本思路
滑动窗口适合处理一部分连续子串或连续子数组的问题，尤其是需要寻找满足特定条件的区间时。
最直接的方法是枚举所有可能的子串。对于长度为 n 的字符串，仅起点和终点的组合就有 个，如果还要逐个检查子串内部的元素，时间开销就会更大。
不过，仔细想想，相邻的两个子串可能有大量重复的元素。如果每次都重新遍历整个区间，就会产生许多不必要的计算。
滑动窗口的思路就是：通过移动左右指针来调整区间，并在移动过程中维护窗口内的数据，避免反复检查整个子串。
一般用 left 和 right 两个指针表示窗口边界：
right向右移动，将新元素加入窗口。left向右移动，将左侧元素移出窗口。- 每次移动时，同步更新窗口中的数据，例如字符出现次数、元素之和等。
这里采用左闭右开的区间 [left, right)，因此当前窗口的长度就是：
right - left
虽然滑动窗口的代码经常会出现嵌套的 while 循环，但不一定意味着时间复杂度是 。
因为左右指针都只向前移动，不会回头，每个指针最多移动 n 次。如果每次更新窗口数据的开销都是 ，那么整个窗口维护过程的时间复杂度就可以达到 。
当然，并不是所有子串问题都适合滑动窗口。还需要根据题目条件判断，能否通过单向移动指针来维护所需的窗口状态。
1.1 通用代码框架
下面是我整理的滑动窗口伪代码框架。具体使用什么数据结构、什么时候收缩窗口，都需要根据实际题目进行调整。
# 滑动窗口算法伪码框架
def slidingWindow(s: str):
# 用合适的数据结构记录窗口中的数据，根据具体场景变通
# 比如说，我想记录窗口中元素出现的次数，就用 map
# 如果我想记录窗口中的元素和，就可以只用一个 int
window = ...
left, right = 0, 0
while right < len(s):
# c 是将移入窗口的字符
c = s[right]
window.add(c)
# 增大窗口
right += 1
# 进行窗口内数据的一系列更新
...
# *** debug 输出的位置 ***
# 注意在最终的解法代码中不要 print
# 因为 IO 操作很耗时，可能导致超时
# print(f"window: [{left}, {right})")
# ***********************
# 判断左侧窗口是否要收缩
while left < right and window needs shrink:
# d 是将移出窗口的字符
d = s[left]
window.remove(d)
# 缩小窗口
left += 1
# 进行窗口内数据的一系列更新
...这里的 window.add()、window.remove() 和 window needs shrink 都只是伪代码，表示加入元素、移除元素以及判断窗口是否需要收缩，并不是可以直接运行的 Python 语句。
实际写题时，我会先考虑三个问题：
- 什么时候扩大窗口？
right移动后，新加入的字符会对窗口中的数据产生什么影响？ - 什么时候缩小窗口？ 需要满足什么条件才能移动
left？移除字符后又该更新哪些数据？ - 什么时候更新答案？ 是在窗口满足条件时更新，还是在收缩完成后更新？
把这三个问题想清楚，滑动窗口的整体逻辑通常就比较明确了。
接下来通过几道题，看看不同情况下应该如何维护窗口。
2. LeetCode 76. 最小覆盖子串
这道题要求在字符串 s 中，找到一个长度最短的子串，使它包含字符串 t 中的所有字符，包括重复出现的字符。
例如：
s = "ADOBECODEBANC"
t = "ABC"
答案："BANC"我们可以使用两个字典来维护字符出现的次数：
need：记录目标字符串t中每种字符需要出现多少次。window：记录当前窗口中相关字符已经出现了多少次。
此外，还需要一个变量 vaild，用来统计有多少种字符的出现次数已经达到要求。
这里统计的是满足要求的字符种类数，而不是满足要求的字符总数。
例如，假设 t = "AABC"，那么 need 中有三种字符，只有当 A、B、C 的出现次数都达到各自要求时，vaild 才会等于 len(need)。
2.1 窗口如何移动？
先不断移动 right，扩大窗口。
每加入一个字符，就更新 window 中对应的计数。如果某个字符的出现次数刚好达到 need 中要求的次数，就让 vaild 加一。
当：
vaild == len(need)说明当前窗口已经包含了目标字符串需要的全部字符。
但我们要求的是最短覆盖子串，因此仅仅找到一个满足条件的窗口还不够。
此时应该尝试移动 left，逐渐缩小窗口。
每次收缩前，先判断当前窗口是否比之前记录的答案更短，如果更短，就更新结果。
随后移除左侧字符，并更新相关计数。当某个字符的数量从满足要求变成不足时，vaild 就需要减一。
这样不断重复“扩大窗口 → 满足条件 → 尝试收缩”的过程，就能逐步找到最短的覆盖子串。
2.2 Python 代码
class Solution:
def minWindow(self, s: str, t: str) -> str:
window = dict()
need = dict()
# 把目标串存到目标窗口
for i in t:
need[i] = need.get(i, 0) + 1
vaild = 0
left = right = 0
length = float("inf")
res = ""
while right < len(s):
c = s[right]
right += 1
# 如果字符在need窗口里面就让计数器+1
if c in need:
window[c] = window.get(c, 0) + 1
# 如果这个字符满足条件了，就让vaild+1
if window[c] == need[c]:
vaild += 1
# 当vaild和目标窗口长度相同，就代表所有元素都满足条件了，尝试缩小窗口
while vaild == len(need):
# 此时的子串就是一个符合条件的子串，尝试更新答案
if length > right - left:
res = s[left:right]
length = right - left
c = s[left]
left += 1
# 缩小窗口，更新相关的数据。
if c in need:
if window[c] == need[c]:
vaild -= 1
window[c] -= 1
return res这道题最需要注意的是更新答案的时机。
当窗口已经满足所有字符要求时，我们并不是立刻停止，而是继续收缩左边界，直到窗口不再满足条件。
每次收缩之前，都有机会得到一个更短的答案。
因此，这道题使用的是可变长度的滑动窗口，内层通过 while 不断缩小窗口。
3. LeetCode 567. 字符串的排列
这道题需要判断：字符串 s2 中，是否存在某个子串，恰好是字符串 s1 的一种排列。
例如：
s1 = "ab"
s2 = "eidbaooo"
结果：True因为 s2 中存在子串 "ba"，它恰好是 "ab" 的一种排列。
这道题和上一题有些相似，同样可以使用 need 和 window 两个字典统计字符次数。
不过，这里不需要寻找最短子串，而是判断是否存在一个长度固定的子串。
既然要求找到 s1 的某种排列，那么目标子串的长度必然等于 len(s1)。
因此，我们只需要维护一个长度为 len(s1) 的窗口。
3.1 定长窗口的处理
首先移动 right，不断将字符加入窗口。
每次加入字符后，更新 window 和 vaild。
当窗口长度达到 len(s1) 时，就检查当前窗口中的字符数量是否全部满足要求。
如果：
vaild == len(need)说明找到了符合条件的排列，直接返回 True。
如果不满足，就移除窗口最左侧的字符，再继续向右移动。
这里我使用的是 if，而不是上一题的 while。
原因很简单：窗口每次只加入一个字符，长度最多只会达到目标长度，检查后移出一个字符即可。
因此，不需要像最小覆盖子串那样，反复移动左指针来寻找最短窗口。
3.2 Python 代码
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
need = dict()
window = dict()
for i in s1:
need[i] = need.get(i, 0) + 1
vaild = left = right = 0
while right < len(s2):
c = s2[right]
right += 1
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
vaild += 1
if right - left >= len(s1):
if vaild == len(need):
return True
c = s2[left]
left += 1
if c in need:
if window[c] == need[c]:
vaild -= 1
window[c] -= 1
return False这里的窗口在达到目标长度后，先判断是否满足条件，再移出最左侧字符。
由于每轮循环只加入一个字符，移出一个字符后，窗口就会恢复到比目标长度小一的位置，方便下一轮继续检查。
如果遍历完整个 s2 都没有找到满足要求的窗口，就返回 False。
4. LeetCode 438. 找到字符串中所有字母异位词
这道题的思路与第 567 题基本相同。
我们需要在字符串 s 中，找到所有与 p 互为字母异位词的子串，并返回它们的起始索引。
例如：
s = "cbaebabacd"
p = "abc"
答案：[0, 6]因为 "cba" 和 "bac" 都是 "abc" 的字母异位词，分别从索引 0 和 6 开始。
由于字母异位词的长度一定相同，所以仍然可以使用长度为 len(p) 的定长滑动窗口。
与上一题的区别主要在于答案的处理方式。
第 567 题只需要判断是否存在符合条件的子串，找到后就能直接返回 True。
但这道题要求返回所有满足条件的位置，因此不能提前结束，而是要继续向右滑动窗口。
每当窗口中的字符数量全部满足要求时，就将当前窗口的左端点 left 加入结果列表。
4.1 Python 代码
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
need = dict()
windows = dict()
vaild = left = right = 0
res = []
for i in p:
need[i] = need.get(i, 0) + 1
while right < len(s):
c = s[right]
right += 1
if c in need:
windows[c] = windows.get(c, 0) + 1
if windows[c] == need[c]:
vaild += 1
if right - left >= len(p):
if vaild == len(need):
res.append(left)
c = s[left]
left += 1
if c in need:
if windows[c] == need[c]:
vaild -= 1
windows[c] -= 1
return res可以发现，这份代码与第 567 题非常接近。
窗口的扩大、缩小以及字符计数方式都没有变化，只是将找到答案时的：
return True改成了：
res.append(left)最后再返回整个结果列表。
这两道题放在一起理解比较方便，因为它们本质上使用的是同一种定长窗口，只是对答案的要求不同。
5. LeetCode 3. 无重复字符的最长子串
最后这道题要求找到字符串中不包含重复字符的最长连续子串，并返回它的长度。
例如：
s = "abcabcbb"
答案：3因为 "abc" 是一个不含重复字符的子串，长度为 3，并且不存在更长的合法子串。
与前面的题目相比，这次不需要 need 字典，因为没有指定必须包含哪些字符。
我们只需要维护一个 window，记录当前窗口中每个字符出现的次数。
5.1 遇到重复字符时收缩窗口
首先移动右指针，将新字符加入窗口，并更新它的出现次数。
如果加入之后，当前字符出现了两次或更多次，就说明窗口中产生了重复字符。
此时需要移动 left，不断移除窗口左侧的字符，直到重复被消除。
例如：
s = "abca"当右指针移动到最后一个 a 时，窗口中包含：
a b c a由于 a 重复出现，需要将左侧第一个 a 移出窗口。
窗口就变成了：
b c a此时不再包含重复字符，可以继续向右移动。
因为每次加入新字符之前，窗口都已经没有重复字符，所以只需要处理这次新加入的字符是否重复。
等内层 while 循环结束后，当前窗口一定是一个不含重复字符的合法子串。
此时就可以用窗口长度更新答案：
if right - left > length:
length = right - left5.2 Python 代码
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = right = 0
window = dict()
length = 0
while right < len(s):
c = s[right]
right += 1
window[c] = window.get(c, 0) + 1
while window[c] >= 2:
new_c = s[left]
left += 1
window[new_c] -= 1
if right - left > length:
length = right - left
return length这道题和第 76 题一样，都需要通过 while 动态收缩窗口。
不过，两道题的收缩条件不同：
- 最小覆盖子串：窗口已经满足要求时，尝试缩小窗口，寻找更短的答案。
- 无重复字符的最长子串：窗口出现重复字符时，必须缩小窗口，直到重新满足要求。
因此，两道题虽然都使用可变长度的滑动窗口，但更新答案的时机恰好不同。
第 76 题是在窗口满足覆盖条件时更新最短答案，而第 3 题是在消除重复字符之后，更新最长答案。
6. 总结
通过这四道题，可以发现滑动窗口虽然有相对固定的代码框架，但具体什么时候收缩窗口、什么时候更新答案，仍然需要根据题目调整。
| 题目 | 窗口类型 | 收缩条件 | 更新答案的时机 |
|---|---|---|---|
| 76. 最小覆盖子串 | 可变窗口 | 满足覆盖条件时尝试收缩 | 收缩前记录更短的窗口 |
| 567. 字符串的排列 | 定长窗口 | 达到目标长度时移出一个字符 | 检查到符合条件的排列 |
| 438. 找到所有字母异位词 | 定长窗口 | 达到目标长度时移出一个字符 | 记录所有合法窗口的起点 |
| 3. 无重复字符的最长子串 | 可变窗口 | 出现重复字符时收缩 | 消除重复后记录最长长度 |
对于这几道题，在哈希表操作平均为常数时间的前提下，左右指针都只会向前移动，因此窗口维护本身具有线性的时间复杂度。
不过，实际代码中的其他操作也需要考虑。例如第 76 题使用字符串切片保存答案，切片会产生额外的复制开销。
我觉得写滑动窗口时，最重要的不是记住某一份固定模板，而是先想清楚：
窗口中需要维护什么数据？什么时候扩大或缩小窗口？什么时候更新答案？
只要明确这三个问题，再结合题目要求调整代码，就能更容易地理解不同滑动窗口题目的解法。
聊两句
评论审核后显示有疑问、补充，或者想交流一下，都可以写在这里。
评论区将在滚动到这里时加载。