子串 / 子数组类问题（最长、最短、刚好满足某条件）优先想滑动窗口。
通用模板
from collections import Counter
def min_window(s, target):
need = Counter(target)
missing = len(target)
left = best_start = 0
best = float('inf')
for right, ch in enumerate(s):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
while missing == 0: # 窗口满足，尝试缩左边界
if right - left + 1 < best:
best, best_start = right - left + 1, left
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return s[best_start:best_start + best] if best != float('inf') else ''
三个关键点
- 右边界只前进，所以整体 O(n)
- 用
missing计数而不是每次重扫窗口，避免退化成 O(n²) - 收缩左边界只在满足条件时进行
什么时候不能用
数组里有负数时，「窗口扩大则和变大」的单调性不成立，窗口法失效，
改成前缀和 + 哈希表。
楼主 · 2026-09-28 14:31 · 浏览 2
