一、问题理解
问题描述
给定两个字符串s和t，返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。
注意：
对于
t中重复字符，子串中该字符数量必须不少于t中该字符数量。如果存在这样的子串，题目保证它是唯一的答案。
示例
text
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小子串 "BANC" 包含 'A'、'B' 和 'C' 输入：s = "a", t = "a" 输出："a" 输入：s = "a", t = "aa" 输出："" 解释：t 中有两个 'a'，但 s 中只有一个 'a'
二、核心思路：滑动窗口 + 字符计数
暴力解法的局限性
枚举s中所有子串并检查是否包含t的所有字符，时间复杂度为 O(n³)，效率极低。
滑动窗口优化思路
字符频率统计：用哈希表（Counter）记录
t中每个字符的出现次数。滑动窗口维护：用左右指针
left和right表示当前窗口。扩展窗口：
right指针向右移动，扩大窗口，直到窗口包含t的所有字符。收缩窗口：当窗口包含
t的所有字符时，移动left指针，缩小窗口，寻找最小子串。更新结果：记录满足条件的最小窗口。
三、代码逐行解析
python
from collections import Counter from typing import List class Solution: def minWindow(self, s: str, t: str) -> str: # 1. 初始化计数器 # cnt_s: 记录当前窗口中字符的出现次数 # cnt_t: 记录t中字符的出现次数 cnt_s = Counter() cnt_t = Counter(t) # 2. 初始化结果边界 # ans_left, ans_right 记录最小窗口的边界 # 初始设置为不可能的值，便于后续更新 ans_left, ans_right = -1, len(s) # 3. 滑动窗口左指针 left = 0 # 4. 遍历字符串s，right是窗口右边界 for right, c in enumerate(s): # 4.1 将当前字符加入窗口计数器 cnt_s[c] += 1 # 4.2 当窗口包含t的所有字符时，尝试收缩窗口 while cnt_s >= cnt_t: # 4.2.1 如果当前窗口更小，更新结果 if right - left < ans_right - ans_left: ans_left, ans_right = left, right # 4.2.2 将左边界字符移出窗口 cnt_s[s[left]] -= 1 # 如果字符计数为0，从计数器中删除 if cnt_s[s[left]] == 0: del cnt_s[s[left]] # 4.2.3 左指针右移，收缩窗口 left += 1 # 5. 返回结果 # 如果ans_left仍为-1，说明没有找到符合条件的窗口 return "" if ans_left < 0 else s[ans_left:ans_right + 1]
四、关键步骤详解
1. 字符计数初始化
python
cnt_s = Counter() # 窗口字符计数器 cnt_t = Counter(t) # t的字符计数器
cnt_t记录了t中每个字符需要出现的次数cnt_s动态记录当前窗口中每个字符的出现次数
2. 滑动窗口维护
python
for right, c in enumerate(s): cnt_s[c] += 1 # 扩展窗口 while cnt_s >= cnt_t: # 当窗口包含t的所有字符时 # 更新最小窗口 if right - left < ans_right - ans_left: ans_left, ans_right = left, right # 收缩窗口 cnt_s[s[left]] -= 1 if cnt_s[s[left]] == 0: del cnt_s[s[left]] left += 1
关键点：
cnt_s >= cnt_t：这是Python Counter的一个特性，表示对于cnt_t中的每个键，cnt_s中对应的值都大于等于它当窗口满足条件时，我们尝试收缩窗口以找到更小的满足条件的窗口
3. 边界条件处理
python
return "" if ans_left < 0 else s[ans_left:ans_right + 1]
如果
ans_left仍然是初始值 -1，说明没有找到符合条件的窗口，返回空字符串否则返回最小窗口子串
五、优化版本（使用数组代替Counter）
对于ASCII字符，我们可以使用固定大小的数组来提高效率：
python
class Solution: def minWindow(self, s: str, t: str) -> str: # 使用数组记录字符计数（ASCII字符共128个） need = [0] * 128 # t中字符需要的数量 window = [0] * 128 # 窗口中字符的数量 # 统计t中字符 for ch in t: need[ord(ch)] += 1 # 初始化 left, right = 0, 0 min_len = float('inf') min_left = 0 # 记录需要匹配的字符种类数 need_count = len(t) match_count = 0 # 滑动窗口 while right < len(s): # 当前字符 ch = s[right] right += 1 # 如果当前字符是t中需要的字符 if need[ord(ch)] > 0: window[ord(ch)] += 1 # 如果窗口中的该字符数量不超过需要的数量，匹配数加1 if window[ord(ch)] <= need[ord(ch)]: match_count += 1 # 当所有字符都匹配时，尝试收缩窗口 while match_count == need_count: # 更新最小窗口 if right - left < min_len: min_len = right - left min_left = left # 左边界字符 left_ch = s[left] left += 1 # 如果左边界字符是t中需要的字符 if need[ord(left_ch)] > 0: # 减少窗口中该字符的计数 window[ord(left_ch)] -= 1 # 如果窗口中的该字符数量少于需要的数量，匹配数减1 if window[ord(left_ch)] < need[ord(left_ch)]: match_count -= 1 # 返回结果 return "" if min_len == float('inf') else s[min_left:min_left + min_len]六、复杂度分析
时间复杂度：O(n + m)
n是字符串s的长度，m是字符串t的长度每个字符最多被访问两次（一次由右指针，一次由左指针）
总体时间复杂度为 O(n)
空间复杂度：O(1)
使用固定大小的数组（128个元素）或有限的Counter
空间消耗与输入字符串长度无关
七、实例演示
以s = "ADOBECODEBANC",t = "ABC"为例，演示滑动窗口过程：
初始状态：
cnt_t = {'A':1, 'B':1, 'C':1}left = 0,right = 0窗口为空，不满足条件
扩展窗口：
right移动到 5，窗口为 "ADOBEC"，包含 A、B、C，满足条件开始收缩窗口
收缩窗口：
记录当前窗口 "ADOBEC" (长度 6)
移动
left到 1，窗口为 "DOBEC"，不满足条件（缺少 A）停止收缩
继续扩展：
right移动到 10，窗口为 "DOBECODEBA"，包含 A、B，缺少 Cright移动到 12，窗口为 "DOBECODEBANC"，包含 A、B、C，满足条件开始收缩窗口
再次收缩：
记录当前窗口 "DOBECODEBANC" (长度 12)
移动
left，直到窗口为 "BANC" (长度 4)此时窗口满足条件且是最小窗口
最终结果：
最小窗口为 "BANC"
八、常见问题与解答
Q1: 为什么使用while cnt_s >= cnt_t而不是if？
使用
while循环可以确保在窗口满足条件时，我们不断尝试收缩窗口以找到更小的满足条件的窗口使用
if只会收缩一次，可能错过更小的窗口
Q2: 如何处理t中的重复字符？
cnt_t记录了每个字符需要的数量cnt_s >= cnt_t确保了窗口中每个字符的数量不少于t中该字符的数量
Q3: 如果t中有字符不在s中怎么办？
算法会遍历整个
s，如果找不到满足条件的窗口，最终返回空字符串
Q4: 为什么需要删除计数为0的字符？
当
cnt_s[s[left]]减到0时，如果不删除，cnt_s >= cnt_t的比较可能会出错例如，如果
t中没有某个字符，但cnt_s中有这个字符且计数为0，比较时这个字符不会影响结果
九、相关题目
1. LeetCode 567. 字符串的排列
python
def checkInclusion(s1: str, s2: str) -> bool: # 判断s2是否包含s1的排列 from collections import Counter cnt_s1 = Counter(s1) cnt_window = Counter() left = 0 for right in range(len(s2)): cnt_window[s2[right]] += 1 # 当窗口大小等于s1长度时 if right - left + 1 == len(s1): if cnt_window == cnt_s1: return True # 移动左指针 cnt_window[s2[left]] -= 1 if cnt_window[s2[left]] == 0: del cnt_window[s2[left]] left += 1 return False
2. LeetCode 438. 找到字符串中所有字母异位词
python
def findAnagrams(s: str, p: str) -> List[int]: # 找到s中所有p的字母异位词的起始索引 from collections import Counter cnt_p = Counter(p) cnt_window = Counter() result = [] left = 0 for right in range(len(s)): cnt_window[s[right]] += 1 # 当窗口大小等于p长度时 if right - left + 1 == len(p): if cnt_window == cnt_p: result.append(left) # 移动左指针 cnt_window[s[left]] -= 1 if cnt_window[s[left]] == 0: del cnt_window[s[left]] left += 1 return result
3. LeetCode 3. 无重复字符的最长子串
python
def lengthOfLongestSubstring(s: str) -> int: # 找到不含重复字符的最长子串长度 from collections import defaultdict char_index = {} max_len = 0 left = 0 for right in range(len(s)): if s[right] in char_index and char_index[s[right]] >= left: left = char_index[s[right]] + 1 char_index[s[right]] = right max_len = max(max_len, right - left + 1) return max_len十、总结
核心要点
滑动窗口是关键：用左右指针维护当前窗口，动态调整窗口大小
字符计数是基础：用哈希表或数组记录字符出现次数，判断窗口是否满足条件
双指针移动策略：
右指针扩展窗口，直到窗口满足条件
左指针收缩窗口，寻找最小满足条件的窗口
优化技巧
使用数组代替哈希表：对于固定字符集（如ASCII），使用数组可以提高效率
记录匹配字符数：使用
match_count变量记录已匹配的字符数，避免每次比较整个哈希表提前终止：如果找到长度为
len(t)的窗口，可以直接返回，因为这是可能的最小窗口
适用场景
需要在字符串中寻找满足特定条件的子串
条件通常与字符出现次数有关
要求时间复杂度为 O(n)
掌握滑动窗口+字符计数的解法，不仅能够解决最小覆盖子串问题，还能够解决一系列类似的字符串匹配问题，是面试中非常重要的算法技巧。
)
)
