【LeetCode HOT100 】：最小覆盖子串——滑动窗口的经典应用题解

题目概述题目名称76. 最小覆盖子串难度困难题目链接https://leetcode.cn/problems/minimum-window-substring/题目描述给定两个字符串s和t返回s中涵盖t所有字符的最小子串。如果不存在则返回空字符串。关键点涵盖意味着s子串中每个字符的数量必须不少于t中该字符的数量答案唯一且连续子串时间复杂度要求较高数据规模可达 10^5示例text输入s ADOBECODEBANC, t ABC 输出BANC解题思路总览本题属于滑动窗口的经典应用。核心思路是维护一个动态窗口通过移动右指针扩展窗口直至覆盖t中所有字符再移动左指针收缩窗口以寻找最短覆盖子串。解法时间复杂度空间复杂度适用场景滑动窗口 哈希表O(n)O(k)通用k为字符集大小滑动窗口 数组O(n)O(128)仅限ASCII字符优化滑动窗口去冗余O(n)O(n)字符重复率高的场景解法一滑动窗口 哈希表通用解法核心思想使用两个哈希表need记录字符串t中每个字符的需求数量window记录当前窗口中每个字符的出现次数维护一个valid变量表示当前窗口中已满足需求量的字符种类数。当valid need.size()时说明当前窗口已覆盖t此时尝试收缩左边界。算法步骤初始化left 0valid 0最小长度minLen ∞右指针right遍历s将s[right]加入窗口如果该字符是需要的且窗口内数量达到需求valid当valid need.size()时更新最短子串的起始位置和长度尝试移动左指针收缩窗口左移前如果左边界字符是需要的且窗口内数量刚好等于需求valid--左边界字符移出窗口left返回最短子串代码实现Pythonpythonclass Solution: def minWindow(self, s: str, t: str) - str: from collections import defaultdict need defaultdict(int) for c in t: need[c] 1 window defaultdict(int) left 0 valid 0 start 0 min_len float(inf) for right in range(len(s)): c s[right] if c in need: window[c] 1 if window[c] need[c]: valid 1 while valid len(need): if right - left 1 min_len: min_len right - left 1 start left d s[left] left 1 if d in need: if window[d] need[d]: valid - 1 window[d] - 1 return s[start:start min_len] if min_len ! float(inf) else 代码实现Javajavaclass Solution { public String minWindow(String s, String t) { MapCharacter, Integer need new HashMap(); MapCharacter, Integer window new HashMap(); for (char c : t.toCharArray()) { need.put(c, need.getOrDefault(c, 0) 1); } int left 0, valid 0; int start 0, minLen Integer.MAX_VALUE; for (int right 0; right s.length(); right) { char c s.charAt(right); if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) 1); if (window.get(c).equals(need.get(c))) { valid; } } while (valid need.size()) { if (right - left 1 minLen) { minLen right - left 1; start left; } char d s.charAt(left); left; if (need.containsKey(d)) { if (window.get(d).equals(need.get(d))) { valid--; } window.put(d, window.get(d) - 1); } } } return minLen Integer.MAX_VALUE ? : s.substring(start, start minLen); } }解法二滑动窗口 数组ASCII优化版核心思想由于题目中的字符由英文字母组成可以使用长度为 128 的数组代替哈希表效率更高。数组下标直接对应字符的 ASCII 码。代码实现Pythonpythonclass Solution: def minWindow(self, s: str, t: str) - str: need [0] * 128 for c in t: need[ord(c)] 1 window [0] * 128 left 0 count 0 # 已满足需求的字符总数非种类 min_len float(inf) start 0 for right in range(len(s)): idx ord(s[right]) window[idx] 1 if window[idx] need[idx]: count 1 while count len(t): if right - left 1 min_len: min_len right - left 1 start left left_idx ord(s[left]) if window[left_idx] need[left_idx]: count - 1 window[left_idx] - 1 left 1 return s[start:start min_len] if min_len ! float(inf) else 注意此版本使用count统计已满足需求的字符总数而非种类数逻辑略有不同但效果相同。解法三优化滑动窗口预处理有效字符核心思想当字符串s很长但t很短时s中大部分字符可能都不在t中。可以预先过滤掉这些无效字符只保留s中出现在t里的字符及其下标然后在过滤后的序列上应用滑动窗口。适用场景s长度很大如 10^5t长度很小s中属于t的字符占比很低算法步骤遍历s记录所有属于t的字符及其在s中的下标在过滤后的字符序列上执行滑动窗口根据下标还原原字符串中的子串位置代码实现Pythonpythonclass Solution: def minWindow(self, s: str, t: str) - str: from collections import defaultdict, Counter need Counter(t) filtered [(i, ch) for i, ch in enumerate(s) if ch in need] left 0 window defaultdict(int) valid 0 start 0 min_len float(inf) for right in range(len(filtered)): idx, ch filtered[right] window[ch] 1 if window[ch] need[ch]: valid 1 while valid len(need) and left right: left_idx, left_ch filtered[left] curr_len idx - left_idx 1 if curr_len min_len: min_len curr_len start left_idx if window[left_ch] need[left_ch]: valid - 1 window[left_ch] - 1 left 1 return s[start:start min_len] if min_len ! float(inf) else 复杂度分析对比解法时间复杂度空间复杂度说明哈希表滑动窗口O(n)O(k)k为字符集大小通用性最强数组滑动窗口O(n)O(128)常数级空间执行效率最高过滤优化版O(n m)O(m)m为过滤后字符数适合特定场景注n len(s)m len(t)易错点总结valid的含义代表已满足数量要求的字符种类数而非字符总数。当某字符的窗口计数恰好等于需求计数时才增加valid。窗口收缩条件必须使用while而非if因为收缩后窗口可能仍然满足覆盖条件需要持续收缩。边界处理当min_len仍为无穷大时返回空字符串。字符重复处理t中可能包含重复字符如aa需要确保窗口中有至少两个a。相关题目推荐题目难度关联点3. 无重复字符的最长子串中等滑动窗口基础438. 找到字符串中所有字母异位词中等固定窗口滑动567. 字符串的排列中等窗口内字符计数匹配30. 串联所有单词的子串困难多模式串滑动窗口参考链接题目链接LeetCode 76. 最小覆盖子串官方题解如果这篇文章对你有帮助欢迎点赞、收藏、关注