本文针对 LeetCode 76. 最小覆盖子串 问题提供完整的解题思路、多解法代码实现及深度解析覆盖暴力解法、滑动窗口双指针最优解法重点突破“O(m n) 时间复杂度”的进阶要求帮助开发者理解问题本质、掌握滑动窗口的灵活应用规避常见误区。本题核心考点为滑动窗口的动态维护、哈希表的计数应用是面试高频中等难度题目适配算法进阶练习。一、题目核心解读1.1 题目描述精简版给定两个字符串 s长度 m和 t长度 n返回 s 中包含 t 所有字符包括重复字符的最短窗口子串若不存在这样的子串返回空字符串 “”。测试用例保证答案唯一。核心约束与进阶要求数据范围1 ≤ m, n ≤ 10⁵s 和 t 仅由英文字母组成区分大小写如 ‘A’ 和 ‘a’ 视为不同字符。关键要求子串需“覆盖 t 的所有字符”包括重复出现的字符如 t “aa”子串需包含至少两个 ‘a’。进阶要求设计 O(m n) 时间复杂度的算法核心考点也是实际面试中重点考察的方向。1.2 示例解析直观理解示例 1输入 s “ADOBECODEBANC”, t “ABC”解析t 包含 ‘A’、‘B’、‘C’ 各1个s 中包含这三个字符的子串有 “ADOBEC”长度6、“BECODEBA”长度7、“BANC”长度4其中最短的是 “BANC”输出 “BANC”。示例 2输入 s “a”, t “a”解析s 本身就是包含 t 所有字符的子串且长度最短输出 “a”。示例 3输入 s “a”, t “aa”解析t 要求包含两个 ‘a’但 s 只有一个 ‘a’无法满足输出 “”。关键观察本题的核心是“找到最短的子串满足子串中 t 的每个字符含重复的出现次数 ≥ t 中对应字符的出现次数”。暴力解法会因时间复杂度过高超时滑动窗口是最优思路可实现 O(m n) 时间复杂度。二、解题思路深度剖析2种解法从暴力到最优本题的核心矛盾是“时间复杂度”与“子串有效性判断”暴力解法通过枚举所有子串判断有效性时间复杂度过高滑动窗口通过双指针动态维护子串范围结合哈希表计数判断有效性实现高效求解。以下逐一解析每种解法的思路、优缺点及适用场景。2.1 解法1暴力解法基础思路适合理解问题本质2.1.1 思路核心枚举 s 中所有可能的子串判断每个子串是否包含 t 的所有字符含重复记录满足条件的最短子串。具体步骤用哈希表字典统计 t 中每个字符的出现次数记为 t_count作为判断子串有效性的标准。枚举所有子串遍历 s 的所有起始索引 i从 i 开始向后扩展终点索引 j得到子串 s[i…j]。判断子串有效性用哈希表统计子串 s[i…j] 中每个字符的出现次数记为 window_count若 window_count 中所有 t 中的字符的出现次数 ≥ t_count 中的对应次数则该子串有效。记录最短有效子串不断更新满足条件的子串长度保留最短的子串。2.1.2 优缺点优点思路简单、逻辑直观适合新手理解“覆盖子串”的核心要求无需复杂的数据结构技巧。缺点时间复杂度极高为 O(m² × n)。枚举所有子串的时间为 O(m²)每个子串的有效性判断需要遍历子串和 tO(m n)当 m10⁵ 时运算量远超时间限制必然超时仅适合 m ≤ 100 的小数据量。2.2 解法2滑动窗口双指针解法最优解法满足进阶要求2.2.1 思路核心利用“滑动窗口”双指针 left、right 界定窗口范围动态维护子串结合两个哈希表t_count 统计 t 的字符计数window_count 统计当前窗口的字符计数通过“扩大窗口找有效子串、缩小窗口找最短子串”的思路实现 O(m n) 时间复杂度。核心原则滑动窗口维护规则初始化用 t_count 统计 t 中每个字符的出现次数window_count 初始为空用于统计当前窗口内的字符次数left 指针初始为 0用于界定窗口左边界min_len 记录最短有效子串的长度初始为无穷大start 记录最短有效子串的起始索引初始为 0。扩大窗口right 指针右移从 s 的起始位置开始right 指针逐步右移将当前字符 s[right] 加入 window_count若字符在 t_count 中才更新 window_count否则无需统计因为不影响子串有效性。判断窗口有效性当 window_count 中所有 t 的字符的出现次数 ≥ t_count 中的对应次数时说明当前窗口是有效子串此时尝试缩小窗口寻找更短的有效子串。缩小窗口left 指针右移在窗口有效的前提下逐步右移 left 指针缩小窗口范围同时更新 window_count若当前字符在 t_count 中减少其计数每缩小一次判断窗口是否仍有效若有效则更新 min_len 和 start直到窗口无效。重复步骤 2-4直到 right 指针遍历完 s最终根据 min_len 是否为无穷大返回最短子串或空字符串。2.2.2 关键优化有效性判断的高效实现若每次判断窗口有效性都遍历 t_count 对比 window_count会导致时间复杂度上升至 O(m × n)无法满足进阶要求。因此引入“匹配计数器”match优化判断逻辑match 初始为 0代表当前窗口中满足“出现次数 ≥ t_count 对应次数”的字符个数。当 window_count 中某字符的计数达到 t_count 中该字符的计数时match 加 1仅加 1 一次避免重复计数。当 match 等于 t_count 的长度即 t 中所有不同字符都满足计数要求时窗口有效无需遍历对比直接进入缩小窗口阶段。该优化将有效性判断的时间从 O(n) 降至 O(1)确保整体时间复杂度为 O(m n)。2.2.3 思路验证结合示例1s “ADOBECODEBANC”, t “ABC”t_count {‘A’:1, ‘B’:1, ‘C’:1}match 初始为 0min_len 无穷大start 0left 0。right0s[0]‘A’window_count[‘A’]1等于 t_count[‘A’]match1 → 窗口无效match≠3继续扩大。right1s[1]‘D’不在 t_count 中不更新 window_count → 窗口无效。right2s[2]‘O’不在 t_count 中 → 窗口无效。right3s[3]‘B’window_count[‘B’]1等于 t_count[‘B’]match2 → 窗口无效。right4s[4]‘E’不在 t_count 中 → 窗口无效。right5s[5]‘C’window_count[‘C’]1等于 t_count[‘C’]match3 → 窗口有效ADOBEC长度6。更新 min_len6start0。开始缩小窗口left0s[0]‘A’window_count[‘A’]0小于 t_count[‘A’]match2 → 窗口无效停止缩小left1。继续扩大 right 至 10s[10]‘B’、right11s[11]‘A’、right12s[12]‘N’、right13s[13]‘C’过程中不断维护 window_count 和 match当 right13 时窗口为 “BANC”left10match3有效长度4更新 min_len4start10。最终最短子串为 s[10:14] “BANC”与示例一致。2.2.4 优缺点优点时间复杂度 O(m n)t_count 统计 t 的字符需 O(n)right 和 left 指针各遍历 s 一次需 O(m)整体高效满足进阶要求空间复杂度 O(n)哈希表存储 t 的字符计数最多存储 t 中所有不同字符不超过26×252个因为英文字母分大小写空间开销固定。缺点思路相对复杂需同时维护双指针、两个哈希表和匹配计数器容易出现细节错误如窗口缩小时机、match 计数逻辑、字符是否在 t 中的判断。2.3 常见误区提醒误区1忽略 t 中重复字符的要求如示例3t“aa”子串需包含至少两个 ‘a’仅判断字符是否存在不判断出现次数导致错误。误区2有效性判断未优化每次都遍历 t_count 对比 window_count导致时间复杂度过高无法通过大数据量测试。误区3缩小窗口时未判断当前字符是否在 t_count 中就更新 window_count导致计数混乱影响 match 判断。误区4未记录最短子串的起始索引仅记录长度最终无法正确截取子串或初始 min_len 设为 0导致无法区分“无有效子串”和“有效子串长度为0”实际不可能。误区5区分大小写错误如将 ‘A’ 和 ‘a’ 视为同一字符导致测试用例失败。三、代码实现Python2种解法重点最优解法严格按照题目要求的类和方法名格式编写注题目要求方法名为 findKthBit此处按题目实际需求调整为 minWindow贴合题目场景避免混淆代码简洁高效附带详细注释适配 Python 语法规范。3.1 解法1暴力解法仅供理解不推荐提交fromcollectionsimportdefaultdictclassSolution:defminWindow(self,s:str,t:str)-str:m,nlen(s),len(t)# 若t长度大于s直接返回空字符串不可能有覆盖子串ifnm:return# 统计t中每个字符的出现次数t_countdefaultdict(int)forcint:t_count[c]1# 初始化最短子串相关参数min_lenfloat(inf)result# 枚举所有子串的起始索引iforiinrange(m):# 统计当前子串的字符出现次数window_countdefaultdict(int)# 扩展子串终点索引jforjinrange(i,m):cs[j]ifcint_count:window_count[c]1# 判断当前子串是否有效validTrueforkeyint_count:ifwindow_count.get(key,0)t_count[key]:validFalsebreak# 若有效更新最短子串ifvalid:current_lenj-i1ifcurrent_lenmin_len:min_lencurrent_len results[i:j1]# 找到当前i对应的最短有效子串无需继续扩展jj越大子串越长breakreturnresult3.2 解法2滑动窗口双指针解法最优满足进阶要求推荐面试使用fromcollectionsimportdefaultdictclassSolution:defminWindow(self,s:str,t:str)-str:m,nlen(s),len(t)# 边界判断t比s长直接返回空ifnm:return# 1. 统计t中每个字符的出现次数t_countdefaultdict(int)forcint:t_count[c]1# 2. 初始化滑动窗口相关参数window_countdefaultdict(int)# 当前窗口的字符计数match0# 匹配计数器满足计数要求的字符个数left0# 窗口左边界min_lenfloat(inf)# 最短有效子串长度start0# 最短有效子串的起始索引# 3. 扩大窗口right指针右移forrightinrange(m):cs[right]# 仅统计t中存在的字符ifcint_count:window_count[c]1# 当该字符的计数达到t中的要求时match加1仅加一次ifwindow_count[c]t_count[c]:match1# 4. 窗口有效match等于t中不同字符的个数缩小窗口whilematchlen(t_count):# 更新最短有效子串current_lenright-left1ifcurrent_lenmin_len:min_lencurrent_len startleft# 左指针右移缩小窗口left_cs[left]ifleft_cint_count:# 若当前字符是t中的字符更新window_countwindow_count[left_c]-1# 若计数低于t中的要求match减1窗口变为无效ifwindow_count[left_c]t_count[left_c]:match-1# 左指针右移left1# 5. 判断是否存在有效子串返回结果returns[start:startmin_len]ifmin_len!float(inf)else四、代码逐行解析重点讲解最优解法4.1 边界判断与初始化m,nlen(s),len(t)ifnm:returnt_countdefaultdict(int)forcint:t_count[c]1window_countdefaultdict(int)match0left0min_lenfloat(inf)start0解释m、n 分别存储 s 和 t 的长度若 t 比 s 长不可能存在覆盖子串直接返回空字符串。t_count用默认字典统计 t 中每个字符的出现次数如 t“ABC”t_count {‘A’:1, ‘B’:1, ‘C’:1}。window_count统计当前滑动窗口内t 中存在的字符的出现次数无关字符不统计。match匹配计数器记录当前窗口中“出现次数 ≥ t_count 对应次数”的字符个数当 match len(t_count) 时窗口有效。left滑动窗口的左边界初始为 0。min_len记录最短有效子串的长度初始为无穷大方便后续更新。start记录最短有效子串的起始索引用于最终截取子串。4.2 扩大窗口right指针右移forrightinrange(m):cs[right]ifcint_count:window_count[c]1ifwindow_count[c]t_count[c]:match1解释right 指针从 0 遍历到 m-1逐步扩大窗口范围每次获取当前字符 c s[right]。若 c 是 t 中的字符存在于 t_count 中才更新 window_count避免统计无关字符节省空间和时间。当 window_count[c] 等于 t_count[c] 时说明该字符的计数满足要求match 加 1仅加一次避免重复计数例如 t 中 ‘A’ 出现2次window_count[‘A’] 从1变为2时match 才加1。4.3 缩小窗口left指针右移whilematchlen(t_count):current_lenright-left1ifcurrent_lenmin_len:min_lencurrent_len startleft left_cs[left]ifleft_cint_count:window_count[left_c]-1ifwindow_count[left_c]t_count[left_c]:match-1left1解释while 循环条件match len(t_count)即当前窗口有效包含 t 所有字符且满足重复次数要求。更新最短子串计算当前窗口长度 current_len若比 min_len 小更新 min_len 和 start记录新的最短子串起始位置。left_c s[left]获取当前窗口左边界的字符准备右移左边界缩小窗口。若 left_c 是 t 中的字符更新 window_count[left_c]减1因为该字符将离开窗口。若 window_count[left_c] 减1后小于 t_count[left_c]说明该字符的计数不再满足要求match 减1窗口变为无效退出 while 循环继续扩大窗口。left 指针右移缩小窗口范围尝试寻找更短的有效子串。4.4 结果返回returns[start:startmin_len]ifmin_len!float(inf)else解释若 min_len 仍为无穷大说明没有找到有效子串返回空字符串 “”。否则根据 start 和 min_len 截取 s 中的最短有效子串返回该子串。五、性能分析与扩展5.1 两种解法性能对比解法时间复杂度空间复杂度适用场景暴力解法O(m² × n)O(n)哈希表存储 t 字符计数小数据量m ≤ 100适合理解问题本质滑动窗口解法O(m n)O(n)哈希表存储 t 字符计数大数据量m ≤ 10⁵面试最优选择满足进阶要求5.2 边界场景适配本题需重点适配4种边界场景确保代码健壮性场景1t 长度大于 s → 返回 “”代码已适配开头直接判断。场景2s 与 t 长度相等 → 若 s t返回 s否则返回 “”代码会正常判断窗口扩大到 rightm-1 时若有效则返回 s否则返回 “”。场景3t 中存在重复字符如 t“aa” → 代码通过 t_count 统计重复次数window_count 需满足计数要求避免遗漏重复字符。场景4s 中存在多个有效子串且答案唯一测试用例保证 → 代码通过不断更新 min_len 和 start确保返回最短的有效子串。5.3 扩展思考面试延伸如何优化空间复杂度答由于 s 和 t 仅由英文字母组成区分大小写可使用数组替代哈希表如用大小为 128 的数组对应 ASCII 码减少哈希表的开销空间复杂度仍为 O(1)固定大小数组。例如t_count [0] * 128t_count[ord©] 1ord© 得到字符的 ASCII 码。若 s 和 t 包含非英文字符如中文、符号如何调整解法答核心思路不变只需将哈希表defaultdict保留无需改为数组因为非英文字符的 ASCII 码范围不确定数组无法覆盖哈希表可灵活存储任意字符的计数。若题目要求“找到所有最短覆盖子串”而非唯一答案如何修改代码答将 start 改为列表存储所有最短有效子串的起始索引当 current_len min_len 时将 start 加入列表最终根据列表中的起始索引截取所有最短子串并返回。滑动窗口的核心思想是什么答滑动窗口的核心是“用双指针界定窗口范围动态维护窗口内的信息避免重复计算”适用于“子串/子数组相关的最值、匹配问题”可将暴力解法的 O(m²) 时间复杂度优化至 O(m)。六、总结与思考6.1 核心知识点滑动窗口双指针的动态维护通过 right 指针扩大窗口找有效子串left 指针缩小窗口找最短子串实现高效遍历。哈希表的计数应用用两个哈希表分别统计 t 和当前窗口的字符计数结合匹配计数器高效判断窗口有效性。时间复杂度优化从暴力解法的 O(m² × n) 优化至 O(m n)核心是“避免重复判断子串有效性”和“双指针仅遍历一次 s”。6.2 解题启示本题是“滑动窗口 哈希表”的经典结合也是面试中高频考察的中等难度题目解题时需注意先明确问题核心不仅要包含 t 的所有字符还要满足重复字符的计数要求这是区别于“包含所有不同字符”的关键。滑动窗口的维护逻辑是重点牢记“扩大窗口找有效缩小窗口找最短”避免出现“缩小窗口时遗漏字符计数更新”的错误。细节决定成败边界判断t 比 s 长、匹配计数器的更新逻辑、最短子串的起始索引记录这些细节直接影响代码的正确性。进阶要求的实现通过匹配计数器优化有效性判断避免遍历对比确保时间复杂度达到 O(m n)这是面试中加分项。6.3 测试用例验证补充4组测试用例确保代码覆盖所有场景测试用例1s “a”, t “a” → 输出 “a”边界场景s 和 t 长度相等。测试用例2s “a”, t “aa” → 输出 “”t 有重复字符s 无法满足。测试用例3s “aa”, t “aa” → 输出 “aa”t 重复字符s 刚好满足。测试用例4s “abac”, t “abc” → 输出 “bac”最短有效子串。将上述用例代入滑动窗口解法代码均能得到正确结果验证代码的正确性和健壮性。