滑动窗口 解题模板

适用场景

子数组/子串的连续性约束问题（最大/最小/包含/覆盖）

通用模板

可变窗口（求最大/最小）

 
# 求满足条件的最大窗口
 
l = 0
 
for r in range(len(s)):
 
    add(s[r])                # 窗口右扩
 
    while not valid():       # 窗口违规时
 
        remove(s[l])         # 左缩
 
        l += 1
 
    update_answer()          # 更新结果
 
# 求满足条件的最小窗口（标准套模板）
 
need = collections.Counter(t)
 
need_cnt = len(t)
 
l = 0
 
for r, c in enumerate(s):
 
    if c in need:
 
        need[c] -= 1
 
        if need[c] >= 0: need_cnt -= 1
 
    while need_cnt == 0:      # 窗口已覆盖
 
        update_answer()
 
        if s[l] in need:
 
            need[s[l]] += 1
 
            if need[s[l]] > 0: need_cnt += 1
 
        l += 1
 

固定窗口

 
window = [0]*26  # 频次数组
 
for i, c in enumerate(s):
 
    window[ord(c)-97] += 1
 
    if i >= k:
 
        window[ord(s[i-k])-97] -= 1
 
    if window == target:  # 频次匹配
 
        res.append(i-k+1)
 

复杂度总结

模式	时间	空间	典型题
可变窗口	O(n)	O(k)	无重复子串、最小覆盖子串
固定窗口	O(n)	O(1)	异位词、排列
单调队列	O(n)	O(k)	滑动窗口最大值

关键要点

• 可变窗口模板：右移→缩左→更新

• 固定窗口模板：加新→去旧→比较

• 什么时候用 while 缩左？什么时候用 if？

• 欠账计数（need_cnt）比 Counter 比较更高效

→ 查看该分类题目：LeetCode学习路线图 > 九、滑动窗口

---

关联题型

关联题型	常见结合方式	典型题目
数组与哈希	哈希表维护窗口状态	3无重复字符最长子串
字符串	子串问题 + 字符计数	76最小覆盖子串
二分查找	窗口大小二分枚举	209长度最小子数组