哈希算法题目：最小窗口子串 题目描述 给定一个字符串 s 和一个字符串 t ，请在 s 中找出包含 t 所有字符的最小子串。如果 s 中不存在这样的子串，返回空字符串 "" 。 注意： t 中字符可能重复，因此子串必须包含 t 中每个字符的相应数量（不少于 t 中频次）。 时间复杂度要求为 O(|s| + |t|)。 示例 输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：s 中最小窗口 "BANC" 包含 A、B、C 各一个（t 的所有字符）。 解题过程 1. 问题分析 核心需求：在 s 中找最短连续子串，覆盖 t 的所有字符（包括频次）。 暴力解法：枚举所有子串，检查是否覆盖 t ，时间复杂度 O(|s|²·|t|)，不可行。 优化思路：使用滑动窗口（双指针）配合哈希表记录字符频次，实现线性扫描。 2. 哈希表的作用 需要快速判断当前窗口是否覆盖 t ： 用哈希表 need 记录 t 中每个字符的所需频次（如 t="AABC" ，则 need['A']=2, need['B']=1, need['C']=1 ）。 用哈希表 window 记录当前窗口中每个字符的实际频次。 关键指标：定义 valid 变量表示当前窗口中满足 need 频次要求的字符种类数（例如窗口有 2 个 A、1 个 B、1 个 C，则 valid=3，因为 A、B、C 均满足需求）。 3. 滑动窗口算法步骤 初始化 ： 将 t 的字符及频次存入 need 。 定义左右指针 left=0, right=0 ，窗口区间为 [left, right) （左闭右开）。 valid=0 表示当前满足条件的字符种类数。 右指针扩张 （找可行解）： 循环移动 right 指针，将 s[right] 加入窗口： 若 s[right] 在 need 中，则增加 window 中该字符的计数。 若 window 中该字符的计数等于 need 中的需求， valid 加 1。 当 valid == need.size() 时，说明当前窗口已覆盖 t 。 左指针收缩 （优化解）： 在 valid == need.size() 的前提下，循环移动 left 指针缩小窗口： 记录当前窗口长度和起始位置（如果更短则更新结果）。 若 s[left] 在 need 中，则减少 window 中该字符的计数。 若减少后该字符计数低于 need 中的需求， valid 减 1（窗口不再满足条件）。 继续移动 right 寻找下一个可行窗口。 终止条件 ： right 遍历完 s 。 4. 详细示例演示（s="ADOBECODEBANC", t="ABC"） need = {'A':1, 'B':1, 'C':1} 步骤： right=0: 窗口 "A" → window[ A ]=1（满足 need），valid=1。 right=1~5: 窗口 "ADOBEC" → 加入 D、O、B、E、C，当 C 加入后，window[ B]=1, window[ C ]=1，valid=3（满足条件）。 收缩 left： 当前窗口 "ADOBEC" 长度=6，记录起始点 start=0, len=6。 left 右移：移除 A → window[ A ]=0，valid=2（不满足），停止收缩。 right 继续右移：窗口变为 "DOBECODEBA"（直到加入 B 和 A 后，window[ A ]=1 重新满足，valid=3）。 收缩 left： 窗口 "ODEBANC" 长度=6，但比之前长，不更新。 继续收缩到 "BANC"：移除 O、D、E、B（注意移除非 t 字符不影响 valid），当移除第一个 B 时，window[ B ]=0，valid=2，停止收缩。此时窗口 "BANC" 长度=4，更新结果。 最终得到最小窗口 "BANC"。 5. 算法复杂度 左右指针各遍历一次 s ，每次操作哈希表 O(1)，整体 O(|s| + |t|)。 6. 关键细节 窗口定义成左闭右开便于计算长度。 使用 valid 避免每次检查整个 need ，提升效率。 注意处理 s 中包含非 t 字符的情况（这些字符不影响 valid ）。