哈希算法题目：最小覆盖子串 题目描述 给定一个字符串 s 和一个字符串 t ，在字符串 s 里找出包含 t 所有字符的最小子串。如果 s 中不存在这样的子串，返回空字符串 "" 。 注意： t 中字符可能重复，子串需包含相同数量的重复字符。 时间复杂度要求为 O(|s| + |t|)。 示例 输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小子串 "BANC" 包含 A、B、C 各一个（且顺序无关）。 解题过程 步骤1：问题分析 需在 s 中找到最短的连续子串，使其覆盖 t 的所有字符（包括重复字符）。 核心思路：使用 滑动窗口 和 哈希表 动态统计字符频率。 哈希表作用： need ：记录 t 中每个字符的需求数量。 window ：记录当前窗口内满足 t 字符的统计情况。 步骤2：初始化哈希表与变量 定义 need 哈希表，遍历 t 统计每个字符出现次数（如 t="AABC" ，则 need['A']=2, need['B']=1, need['C']=1 ）。 定义 window 哈希表，记录当前窗口中属于 t 的字符数量。 定义 valid 变量，表示当前窗口内已满足 need 需求数量的字符种类数（如窗口中有2个A、1个B、1个C，则 valid=3 ，因为A、B、C均满足需求）。 定义左右指针 left=0, right=0 ，初始窗口为空。 步骤3：滑动窗口扩展与收缩 右指针扩展 ： 移动 right ，将 s[right] 加入窗口。 若 s[right] 在 need 中，则增加 window 中该字符计数。若 window[s[right]] == need[s[right]] ，说明该字符需求已满足， valid++ 。 重复直到 valid == need.size() ，即窗口已覆盖 t 所有字符。 左指针收缩 ： 当 valid == need.size() 时，尝试移动 left 缩小窗口。 记录当前窗口长度和起始位置（若更短则更新结果）。 若 s[left] 在 need 中，则减少 window 中该字符计数。若 window[s[left]] < need[s[left]] ，说明该字符不再满足需求， valid-- 。 左指针右移，继续检查窗口。 步骤4：示例演示（s="ADOBECODEBANC", t="ABC"） need = {'A':1, 'B':1, 'C':1} 右指针移动至窗口 "ADOBEC"： 包含A、B、C各一个， valid=3 ，窗口长度=6。 左指针收缩至 "DOBEC"，移除A后 valid=2 ，停止收缩。 右指针继续移动至 "DOBECODEBA"： 重新包含A、B（C仍在）， valid=3 ，窗口长度=10。 左指针收缩至 "ODEBA"，移除D、O、B、E后， valid=2 （B不足）。 右指针移至 "ODEBA" 末尾，再扩展至 "ODEBANC"： 包含A、B、C， valid=3 ，窗口长度=6。 左指针收缩至 "ANC"，移除O、D、E、B后， valid=2 （B不足）。 右指针无法继续扩展，结束。最小窗口为步骤2中的 "BANC"（长度4）。 步骤5：复杂度与边界处理 时间复杂度：左右指针各遍历一次 s ，O(|s|)。 边界案例：若 t 为空或 s 长度小于 t ，直接返回空字符串。 关键点：通过 valid 避免频繁遍历哈希表检查是否覆盖 t 。 通过以上步骤，即可高效找到最小覆盖子串。