【力扣-76. 最小覆盖字串[特殊字符]】Python笔记
滑动窗口（双指针）通用框架
解决子串 / 子数组问题的最优范式，核心是左右指针 + 窗口：
- 右指针：扩大窗口，获取新字符
- 左指针：缩小窗口，优化窗口长度
- 窗口：
[left, right]闭区间，动态维护有效区间
哈希表（defaultdict）计数
- need：统计目标串
t中每个字符的所需次数 - window：统计当前窗口内每个字符的包含次数
- valid 变量：计数窗口中满足
need要求的字符种类数，valid == len(need)表示窗口已覆盖目标串
最小窗口更新逻辑
- 当窗口有效（
valid达标）时，尝试收缩左边界 - 持续更新最小窗口长度和起始索引，最终截取结果
经典算法题：最小覆盖子串（LeetCode 76）
题目描述
给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。
示例：
- 输入：
s = "ADOBECODEBANC", t = "ABC" - 输出：
"BANC"
最优解法：滑动窗口 + 哈希表
核心思路
- 统计
t的字符需求到need，初始化窗口计数器window、有效计数valid、窗口起始索引start和最小长度min_len - 右指针遍历
s，将字符加入窗口，若满足需求则valid+1 - 当
valid达标时，尝试收缩左边界，更新最小窗口 - 收缩时移除左边界字符，若不再满足需求则
valid-1
代码实现
from collections import defaultdict class Solution: def minWindow(self, s: str, t: str) -> str: need = defaultdict(int) window = defaultdict(int) for c in t: need[c] += 1 left = right = 0 valid = 0 start = 0 min_len = float('inf') while right < len(s): char = s[right] right += 1 if char in need: window[char] += 1 if window[char] == need[char]: valid += 1 while valid == len(need): if right - left < min_len: start = left min_len = right - left d = s[left] left += 1 if d in need: if window[d] == need[d]: valid -= 1 window[d] -= 1 return "" if min_len == float('inf') else s[start:start+min_len]关键逻辑详解
窗口有效性判断
valid == len(need)：当前窗口已包含t所有字符且次数达标- 仅在窗口有效时执行左移收缩，确保找到最小窗口
最小窗口更新
start记录最小窗口的起始索引min_len记录最小窗口长度- 最终通过
s[start:start+min_len]截取结果
边界处理
- 初始化
min_len为无穷大，避免初始值干扰 - 若最终
min_len仍为无穷大，说明无有效窗口，返回空串
算法复杂度与拓展
复杂度分析
- 时间复杂度：O(n)，n为
s长度，每个字符最多入窗、出窗各一次 - 空间复杂度：O(m)，m为
t的字符种类数
适用场景拓展
该模板可直接迁移至：
- 字符串最小覆盖 / 包含问题
- 子数组和 / 长度类滑动窗口问题
- 包含指定字符 / 条件的最小区间查找