最小覆盖子串、无重复最长子串、至多K个不同字符——滑动窗口的精准控制
第3课我们学了滑动窗口的基础——固定窗口大小。但面试中的滑动窗口问题往往是变长窗口，窗口大小由条件动态决定。核心模式有两种：
# 变长滑动窗口通用模板
def sliding_window(s):
from collections import Counter
window = Counter()
left = 0
result = ... # 初始化
for right in range(len(s)):
# 1. 扩大窗口: 加入右端元素
window[s[right]] += 1
# 2. 收缩窗口: 循环直到不满足条件
while window_needs_shrink(window):
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
left += 1
# 3. 更新结果
result = update(result, left, right)
return result题目描述：给定字符串 s 和 t，返回 s 中涵盖 t 所有字符（包括重复字符）的最小子串。如果不存在，返回空字符串。
need 记录 t 中每个字符的需求量，window 记录当前窗口中各字符的数量。维护 formed 变量表示"窗口中已满足需求的字符种数"。当 formed == len(need) 时，窗口满足条件，尝试收缩左边界找更小的窗口。
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
need = Counter(t)
window = Counter()
formed = 0 # 已满足需求的字符种数
need_cnt = len(need) # 需要满足的字符种数
left = 0
min_len = float('inf')
min_start = 0
for right, ch in enumerate(s):
# 扩大窗口
window[ch] += 1
if ch in need and window[ch] == need[ch]:
formed += 1
# 收缩窗口
while formed == need_cnt:
# 更新结果
if right - left + 1 < min_len:
min_len = right - left + 1
min_start = left
# 移除左端字符
left_ch = s[left]
if left_ch in need and window[left_ch] == need[left_ch]:
formed -= 1
window[left_ch] -= 1
left += 1
return s[min_start:min_start + min_len] if min_len != float('inf') else ""时间复杂度：O(|s| + |t|)，空间复杂度：O(|字符集|)
formed 计数器。不用每次都遍历 need 检查是否满足，而是当 window[ch] == need[ch] 时 formed++，当 window[ch] < need[ch] 时 formed--。这样判断窗口是否满足只需 O(1)。题目描述：给定一个字符串 s，找到不含重复字符的最长子串的长度。
max(left, last_pos[ch] + 1)，确保窗口内无重复。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
last_pos = {} # 字符 → 最新位置
left = 0
max_len = 0
for right, ch in enumerate(s):
if ch in last_pos:
left = max(left, last_pos[ch] + 1)
last_pos[ch] = right
max_len = max(max_len, right - left + 1)
return max_len时间复杂度：O(n)，空间复杂度：O(min(n, 字符集))
left = max(left, last_pos[ch] + 1) 中的 max！不能直接用 last_pos[ch] + 1，因为 last_pos 中记录的位置可能已经在窗口左边了（已经被跳过）。例如 "abba"，当处理第二个 a 时，last_pos['a']=0，但 left 已经是2了。题目描述：给定一个字符串 s 和整数 k，找到至多包含 k 个不同字符的最长子串的长度。
from collections import Counter
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
if k == 0:
return 0
window = Counter()
left = 0
max_len = 0
for right, ch in enumerate(s):
window[ch] += 1
# 收缩: 直到不同字符数 ≤ k
while len(window) > k:
left_ch = s[left]
window[left_ch] -= 1
if window[left_ch] == 0:
del window[left_ch]
left += 1
max_len = max(max_len, right - left + 1)
return max_len时间复杂度：O(n)，空间复杂度：O(k)
子串问题（字符频率匹配）用哈希计数器，子数组和问题（和为K）用前缀和+哈希：
# 子数组和 = K 的个数 (LC 560)
# 不能用滑动窗口! (因为有负数)
# 用前缀和 + 哈希表
def subarraySum(nums, k):
from collections import Counter
count = Counter({0: 1}) # 前缀和为0出现1次
prefix = 0
result = 0
for num in nums:
prefix += num
result += count[prefix - k] # 前面有多少个prefix-k
count[prefix] += 1
return result