滑动窗口万能模板
滑动窗口是处理「子数组/子串」问题的利器。掌握一个通用模板，可以解决一类问题。
一、核心思想
窗口：数组/字符串中的一个连续区间 [left, right]
初始化 left = right = 0
while right < n:
扩大窗口：加入 right 位置元素
while 窗口满足某个条件:
收缩窗口：移除 left 位置元素，left++
更新结果
right++
二、万能模板
def sliding_window(s):
window = {} # 记录窗口内元素
left = 0
result = ...
for right in range(len(s)):
# 扩大窗口：右指针右移，加入元素
char_right = s[right]
window[char_right] = window.get(char_right, 0) + 1
# 收缩窗口：当窗口不满足条件时，左指针右移
while 窗口不满足条件:
char_left = s[left]
window[char_left] -= 1
if window[char_left] == 0:
del window[char_left]
left += 1
# 更新结果（此时窗口满足条件）
result = max/min(result, right - left + 1)
return result
三、四类变体
1. 固定窗口大小
# 子数组最大平均数 I（LeetCode 643）
def find_max_average(nums, k):
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
max_sum = max(max_sum, window_sum)
return max_sum / k
2. 可变窗口 — 找最小
# 最小覆盖子串（LeetCode 76）
from collections import Counter
def min_window(s, t):
need = Counter(t)
window = {}
left = valid = 0
start, length = 0, float('inf')
for right in range(len(s)):
c = s[right]
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
valid += 1
while valid == len(need):
if right - left + 1 < length:
start, length = left, right - left + 1
d = s[left]
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
left += 1
return "" if length == float('inf') else s[start:start + length]
3. 可变窗口 — 找最大
# 无重复字符的最长子串（LeetCode 3）
def length_of_longest_substring(s):
char_set = set()
left = result = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
result = max(result, right - left + 1)
return result
4. 双窗口（需要维护两个条件）
# 替换后的最长重复字符（LeetCode 424）
def character_replacement(s, k):
count = {}
left = max_freq = result = 0
for right in range(len(s)):
count[s[right]] = count.get(s[right], 0) + 1
max_freq = max(max_freq, count[s[right]])
# 窗口大小 - 最多字符数 = 需要替换的字符数
if (right - left + 1) - max_freq > k:
count[s[left]] -= 1
left += 1
result = max(result, right - left + 1)
return result
四、滑动窗口速查表
| 题号 | 题目 | 窗口类型 | 关键条件 |
|---|---|---|---|
| LeetCode 3 | 无重复字符的最长子串 | 最大可变 | 无重复 |
| LeetCode 76 | 最小覆盖子串 | 最小可变 | 包含所有目标字符 |
| LeetCode 209 | 长度最小的子数组 | 最小可变 | 和 ≥ target |
| LeetCode 239 | 滑动窗口最大值 | 固定大小 | 窗口最大值 |
| LeetCode 438 | 找到所有字母异位词 | 固定大小 | 异位词匹配 |
| LeetCode 424 | 替换后的最长重复字符 | 最大可变 | 替换 ≤ k 次 |
| LeetCode 480 | 滑动窗口中位数 | 固定大小 | 窗口中位数 |
| LeetCode 567 | 字符串的排列 | 固定大小 | 排列匹配 |
五、常见问题
Q: 什么时候用滑动窗口？
- 连续子数组/子串问题
- 条件可转化为窗口内的统计属性
- 单调性：扩大窗口可能破坏条件，缩小可能恢复
Q: 为什么收缩用 while 不用 if？
因为左指针可能需要移动多步才能重新满足条件。
Q: 窗口内的统计用什么数据结构？
- 字符频率：哈希表 / 数组（26/128/256）
- 窗口最值：单调队列（LeetCode 239）
- 窗口中位数：两个堆 / 有序集合
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。