LeetCode 第 76 题：最小覆盖子串（Minimum Window Substring） 题目描述 给你一个字符串 s 和一个字符串 t ，请在字符串 s 中找出包含 t 的所有字符的最小子串。如果 s 中不存在这样的子串，返回空字符串 "" 。 示例 输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小子串 "BANC" 包含 'A'、'B'、'C' 三个字符。 解题思路 这个问题可以使用 滑动窗口（Sliding Window） 结合 哈希表（Hash Table） 来解决。目标是找到 s 中一个最短的连续子串，使得该子串包含 t 的所有字符（包括重复字符）。 步骤详解 初始化哈希表 用哈希表 need 记录 t 中每个字符的出现次数（需求表）。 用哈希表 window 记录当前窗口中每个字符的出现次数（窗口表）。 定义 valid 变量表示当前窗口中满足 need 条件的字符种类数（例如 t 有 3 种字符，则 valid 最大为 3）。 滑动窗口框架 使用双指针 left 和 right 表示窗口的左右边界，初始化为 0。 右指针 right 向右移动，扩大窗口，直到窗口包含 t 的所有字符。 然后左指针 left 向右移动，缩小窗口，同时更新最小子串的起始位置和长度。 重复上述过程直到 right 到达 s 的末尾。 具体操作 右扩窗口 ： 将 s[right] 加入窗口，更新 window[s[right]] 。 如果 s[right] 在 need 中且 window 中该字符数量等于 need 中的需求数量，则 valid++ 。 当 valid 等于 need 的大小（即所有字符需求已满足）时，开始收缩窗口。 左缩窗口 ： 记录当前窗口的起始位置和长度（如果比之前更短）。 将 s[left] 移出窗口，更新 window[s[left]] 。 如果 s[left] 在 need 中且移出后窗口中的数量不再满足需求，则 valid-- 。 左指针右移，继续检查更短的可行窗口。 复杂度分析 时间复杂度：O(|s| + |t|)，左右指针各遍历一次字符串。 空间复杂度：O(|s| + |t|)，用于存储哈希表。 示例推演（s="ADOBECODEBANC", t="ABC"） 初始化： need = {'A':1, 'B':1, 'C':1} ， window 为空， valid=0 。 右指针移动至窗口 "ADOBEC"：此时包含 A、B、C， valid=3 。 左指针收缩：记录子串 "ADOBEC"（长度 6），左移后窗口为 "DOBEC"， valid 减至 2（缺少 A）。 右指针继续移动至 "DOBECODEBA"：重新包含 A、B、C， valid=3 。 左指针收缩：得到 "BANC"（长度 4），为最终答案。 通过滑动窗口动态调整边界，确保以线性时间找到最优解。