题目描述给你两个字符串s和t长度分别是m和n返回s中的最短窗口子串使得该子串包含t中的每一个字符包括重复字符。如果没有这样的子串返回空字符串。测试用例保证答案唯一。示例示例 1 输入s ADOBECODEBANC, t ABC 输出BANC 解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。 示例 2 输入s a, t a 输出a 解释整个字符串 s 是最小覆盖子串。 示例 3 输入s a, t aa 输出 解释t 中两个字符 a 均应包含在 s 的子串中因此没有符合条件的子字符串返回空字符串。提示m s.lengthn t.length1 m, n 10^5s 和 t 由英文字母组成进阶你能设计一个在 O(m n) 时间内解决此问题的算法吗解题思路总览方法核心思想时间复杂度空间复杂度备注滑动窗口双指针扩张-收缩双指针维护窗口O(m n)O(1)推荐解法暴力枚举枚举所有子串再检查O(m^2 * n)O(1)会超时优化暴力先记录t中字符位置再枚举O(m * n)O(n)不够优一、核心解法滑动窗口双指针核心思想使用滑动窗口的思想维护一个包含 t 中所有字符的窗口1. 右指针扩张直到窗口包含 t 中所有字符 2. 收缩左指针找到最短的满足条件的窗口 3. 记录答案继续扩张右指针关键洞察滑动窗口的关键 1. 右指针不断右移扩大窗口 2. 当窗口满足条件时收缩左指针尝试优化 3. 使用两个哈希表 - need: t 中每个字符需要的次数 - window: 当前窗口中每个字符出现的次数 当 window 满足 need 时说明窗口有效。图解s ADOBECODEBANC, t ABC need {A:1, B:1, C:1} 滑动窗口过程 初始状态: left0, right0 window {} needCnt 3 扩张 right0, s[0]D: D 不在 need 中跳过 扩张 right1, s[1]D: D 不在 need 中跳过 扩张 right2, s[2]O: O 不在 need 中跳过 扩张 right3, s[3]B: B 在 need 中 window[B]1, need[B]1, count1 count3? 否继续扩张 扩张 right4, s[4]E: E 不在 need 中跳过 扩张 right5, s[5]C: C 在 need 中 window[C]1, need[C]1, count2 扩张 right6, s[6]O: O 不在 need 中跳过 扩张 right7, s[7]D: O 不在 need 中跳过 扩张 right8, s[8]E: E 不在 need 中跳过 扩张 right9, s[9]B: B 在 need 中 window[B]2, need[B]1, count2 (B已经满足不增加count) 扩张 right10, s[10]A: A 在 need 中 window[A]1, need[A]1, count3 count3 need.size()窗口有效 收缩 left: left0: 窗口 [0,10] ADOBECODEBA 不满足收缩 left1 left1: 窗口 [1,10] DOBECODEBA 不满足收缩 left2 ... left9: 窗口 [9,10] BA 满足记录答案 BA长度2 left10: 收缩窗口 [10,10] A 不满足继续扩张 继续扩张 right11, s[11]N: N 不在 need 中跳过 扩张 right12, s[12]C: C 在 need 中 window[C]2, need[C]1, count3 (C已满足) 窗口有效 收缩 left: left10: 窗口 [10,12] ANC 不满足收缩 left11 left11: 窗口 [11,12] NC 不满足收缩 left12 left12: 窗口 [12,12] C 不满足收缩 left13 right 到达末尾停止 答案: BANC长度为4比 BA 更长但更靠后二、算法流程图输入: s ADOBECODEBANC, t ABC 初始化: need {A:1, B:1, C:1} window {} left 0, right 0 count 0 (已满足的字符种类数) minLen INF, start 0 扩张 right3 (遇到B): window[B], count1 扩张 right5 (遇到C): window[C], count2 扩张 right10 (遇到A): window[A], count3 窗口有效count need.size() 收缩 left: left0 - ADOBECODEBA 无效 left1 - DOBECODEBA 无效 ... left9 - BA 有效记录 minLen2, start9 left10 - A 无效 继续扩张 right12 (遇到C): window[C], count3 窗口有效 收缩 left: left11 - ANC 无效 left12 - C 无效 right 到达末尾结束 输出: BANC (start9, minLen4)三、完整代码实现classSolution{public:stringminWindow(string s,string t){unordered_mapchar,intneed,window;// 记录 t 中每个字符需要的次数for(charc:t){need[c];}intleft0,right0;intcount0;// 已满足的字符种类数intstart0,minLenINT_MAX;while(rights.size()){charcs[right];// 如果字符在 need 中加入 windowif(need.count(c)){window[c];// 当 window[c] 达到 need[c] 时countif(window[c]need[c]){count;}}// 当窗口满足条件时收缩左边界while(countneed.size()){// 更新最小窗口if(right-leftminLen){startleft;minLenright-left;}// 收缩左边界chards[left];// 如果字符在 need 中从 window 中移除if(need.count(d)){// 注意先判断再--if(window[d]need[d]){count--;// 移除后不再满足}window[d]--;}}}returnminLenINT_MAX?:s.substr(start,minLen);}};四、逐行解析unordered_mapchar,intneed,window;need记录 t 中每个字符需要的次数window记录当前窗口中每个字符出现的次数for(charc:t){need[c];}初始化 need统计 t 中每个字符出现的次数intleft0,right0;intcount0;intstart0,minLenINT_MAX;left, right滑动窗口的左右边界count当前窗口中已满足 need 条件的字符种类数start, minLen最小窗口的起始位置和长度while(rights.size()){charcs[right];右指针不断右移扩张窗口if(need.count(c)){window[c];if(window[c]need[c]){count;}}如果当前字符在 need 中加入 window当 window[c] 达到 need[c] 时count这个字符已经满足条件while(countneed.size()){当窗口满足条件时count need.size()收缩左边界尝试优化if(right-leftminLen){startleft;minLenright-left;}更新最小窗口chards[left];if(need.count(d)){if(window[d]need[d]){count--;}window[d]--;}收缩左边界如果移除的字符在 need 中先判断是否会让 count 减少然后从 window 中移除该字符五、count 变量的作用count 表示当前窗口中满足 need 条件的字符种类数。 例如 t ABCneed {A:1, B:1, C:1} 初始: count 0 遇到 A: window[A]1 need[A], count1 遇到 B: window[B]1 need[B], count2 遇到 C: window[C]1 need[C], count3 当 count need.size() 时说明所有字符都满足了条件。 收缩时 移除 A: window[A]0 ! need[A], count 不变 移除 B: window[B]0 ! need[B], count 不变 移除 C: window[C]0 ! need[C], count-- (变为2) count-- 只发生在 window[d] need[d] 时即移除后刚好不再满足。六、与第 567 题字符串的排列对比维度第 76 题 最小覆盖子串第 567 题 字符串的排列问题类型找最短覆盖子串检查是否存在排列窗口大小可变固定为 t 的长度答案最短子串布尔值方法滑动窗口记录最小滑动窗口固定大小七、复杂度分析方法时间复杂度空间复杂度备注滑动窗口O(m n)O(1)推荐最多 128 个字符暴力枚举O(m^2 * n)O(1)会超时优化暴力O(m * n)O(n)不够优详细分析时间复杂度 right 指针最多移动 m 次 left 指针最多移动 m 次 每次移动都是 O(1) 操作 总计O(2m) O(m) 空间复杂度 need 和 window 最多存储 128 个字符ASCII O(1)常数空间八、边界情况分析情况处理方式t 比 s 长直接返回 “”t “a”, s “a”返回 “a”t 中有重复字符need[c] 累加count 只在达到 need 时才增加s 中无 t 的字符right 遍历完count 始终 need.size()返回 “”示例t 有重复字符s AAAB, t AAB need {A:2, B:1} 扩张过程 遇到 A: window[A]1, need[A]2, count0 遇到 A: window[A]2, need[A]2, count1 遇到 A: window[A]3, count1 (已达标不再增加) 遇到 B: window[B]1, need[B]1, count2 count2 need.size()2窗口有效 收缩 移除第一个 A: window[A]2, count2 (仍满足) 移除第二个 A: window[A]1, need[A]2, count-- (变为1) 窗口无效继续扩张九、面试追问 FAQ问题回答要点Q: 为什么 count 只在 window[c] need[c] 时增加因为只有当 window[c] 达到 need[c] 时这个字符才算满足条件Q: 为什么先判断 window[d] need[d] 再 --如果移除后刚好不满足条件count 才需要减少Q: 为什么不直接把 window[d] need[d] 的情况 --因为只有刚好不满足时才减如果 window[d] need[d] 就不需要减Q: 时间复杂度为什么是 O(m n)right 和 left 最多各移动 m 次每次 O(1)Q: 空间复杂度为什么是 O(1)need 和 window 只存储字符ASCII 只有 128 个Q: 如何处理 Unicode 字符用 unordered_map 代替固定数组复杂度不变十、相关题目题目编号题目名称难度核心差异76最小覆盖子串困难基础题滑动窗口567字符串的排列中等检查是否存在覆盖438找到字符串中所有字母异位词中等找所有异位词3无重复字符的最长子串中等最长无重复子串30串联所有单词的子串困难滑动窗口 单词十一、总结要点内容核心思想滑动窗口左右指针扩张收缩关键变量count 表示满足条件的字符种类数判断条件count need.size() 时窗口有效更新逻辑每次扩张后检查是否有效有效则收缩尝试优化时间复杂度O(m n)每个指针最多移动 m 次空间复杂度O(1)字符集大小固定为 128易错点count-- 的时机只在 window[d] need[d] 时最小覆盖子串是滑动窗口的经典问题通过维护一个满足 need 条件的窗口并不断收缩优化实现了 O(m n) 的时间复杂度。