引言：为什么这道题是算法面试高频题？
“最小覆盖子串”（LeetCode 76）是字符串处理领域的经典难题，也是大厂面试中高频出现的算法题。它的核心考点是滑动窗口（双指针）与哈希表的结合运用，不仅要求开发者能写出正确代码，更需要理解 “动态窗口优化” 的底层逻辑 —— 如何在线性时间内找到 “最小且全覆盖” 的子串，避免暴力枚举的低效陷阱。
如果你曾被这道题的复杂逻辑绕晕，或想掌握滑动窗口的通用解题框架，本文将从问题分析、思路设计、代码拆解到实战延伸，带你一步步吃透这道题。
一、问题重述与难点分析
1. 问题定义
给定两个字符串 s（源字符串）和 t（目标字符串），在 s 中找到包含t所有字符的最小子串，要求：
- 子串中 t 的每个字符出现次数 ≥ 其在 t 中的出现次数；
- 若不存在这样的子串，返回空字符串 ""。
示例：
- 输入：s = "ADOBECODEBANC", t = "ABC"
- 输出："BANC"（长度为 4，是所有满足条件的子串中最短的）
2. 核心难点
- 如何快速判断 “窗口是否覆盖 t 所有字符”？（避免逐一比对字符频次）
- 如何在找到有效窗口后，快速收缩到 “最小长度”？（避免冗余字符占用窗口空间）
- 如何保证时间复杂度最优？（暴力枚举 \(O(n^2)\) 会超时，需优化到线性时间）
二、解题思路：滑动窗口 + 哈希表的黄金组合
1. 滑动窗口的核心逻辑
滑动窗口本质是用两个指针（左指针 i、右指针 j）维护一个动态区间 [i, j]，通过 “扩张 - 收缩” 两个动作寻找最优解：
- 扩张：右指针 j 向右移动，将字符加入窗口，直到窗口满足 “覆盖 t 所有字符”（有效窗口）；
- 收缩：左指针 i 向右移动，移除窗口内的冗余字符（非 t 字符或频次超过需求的 t 字符），直到窗口不再满足条件，此时记录当前最小窗口；
- 重复 “扩张 - 收缩”，直到右指针遍历完 s。
2. 哈希表的优化设计
常规思路是用两个哈希表（一个存 t 的字符需求，一个存窗口内字符频次），但这样会增加空间开销和比对成本。本文代码采用单哈希表（ASCII 数组）实现双重功能，是核心优化点：
- 数组长度设为 128（覆盖所有 ASCII 字符），初始值为 0；
- 遍历 t 时，将对应字符的哈希值减 1：用负数标记 “需要的字符及次数”（例如 t="AAB"，则 hash['A']=-2，hash['B']=-1）；
- 遍历 s 时，将窗口内字符的哈希值加 1：通过哈希值的正负 / 大小判断字符状态：
哈希值状态 | 含义 |
字符是 t 所需，且窗口内数量未满足需求 | |
= 0 | 该字符是 t 所需，且窗口内数量刚好满足需求 |
> 0 | 该字符是冗余（窗口内数量超过需求）或非 t 字符 |
3. 关键变量设计
- count：记录窗口中 “已满足需求的 t 字符种类数”（例如 t="ABC"，当窗口中同时有 A、B、C 且数量达标时，count=3）；
- minLen：存储最小窗口的长度，初始化为 s.length()+1（确保初始无有效窗口时，后续可更新）；
- subLeft：存储最小窗口的左边界，初始化为 -1（标记无有效窗口）。
三、代码逐行拆解（带注释 + 逻辑分析）
class Solution {
public:
string minWindow(string s, string t) {
// 1. 初始化哈希表：128位ASCII数组，同时记录t的需求（负数）和窗口频次（动态更新）
vector<int> hash(128, 0);
for (char c : t) hash[c]--; // 标记t中字符的需求：需要k个则为-k
int sLen = s.length(), tLen = t.length();
int count = 0; // 已满足需求的t字符种类数（达到t中该字符的需求次数）
int minLen = sLen + 1; // 最小窗口长度，初始值大于s的最大可能长度
int subLeft = -1; // 最小窗口的左边界，初始为-1表示无有效窗口
// 2. 滑动窗口核心循环：j是右指针（扩张窗口），i是左指针（收缩窗口）
for (int i = 0, j = 0; j ; j++) {
char currentChar = s[j]; // 当前加入窗口的字符
// 2.1 判断当前字符是否是t所需且未满足需求
if (hash[currentChar] 0) {
count++; // 满足一种字符的需求，count加1
}
hash[currentChar]++; // 窗口中该字符频次+1（无论是否是t的字符）
// 2.2 收缩窗口：移除冗余字符（hash[s[i]]>0表示冗余）
while (i < j && hash[s[i]] > 0) {
hash[s[i]]--; // 冗余字符频次减1
i++; // 左指针右移，收缩窗口
}
// 2.3 更新最小窗口：仅当窗口满足覆盖t所有字符（count==tLen）且长度更小时
if (count == tLen && j - i + 1 Len) {
minLen = j - i + 1; // 更新最小长度
subLeft = i; // 更新最小窗口左边界
}
}
// 3. 返回结果：有有效窗口则截取子串，否则返回空字符串
return subLeft >= 0 ? s.substr(subLeft, minLen) : "";
}
};
关键步骤深度解析
步骤 1：哈希表初始化（hash[c]--）
这一步是代码的 “巧思核心”。例如 t="ABC"，遍历后 hash['A']=-1、hash['B']=-1、hash['C']=-1，其他字符为 0。这样设计的好处是：
- 无需额外维护 “需求表” 和 “窗口表”，一个数组搞定两类信息；
- 后续通过 hash[c] 的正负，可直接判断字符是否是 t 所需、是否满足需求。
步骤 2：右指针扩张（j++）
- 每加入一个字符 s[j]，先判断是否是 t 所需且未满足（hash[c]：若是，则 count` 加 1（表示多满足一种字符的需求）；
- 无论是否是 t 的字符，都要 hash[c]++：更新窗口内字符频次，为后续收缩窗口做准备。
步骤 3：左指针收缩（i++）
当 hash[s[i]]>0 时，说明 s[i] 是冗余字符（可能是 t 的字符但频次超了，也可能是非 t 字符），此时收缩窗口：
- 左指针右移，移除该冗余字符；
- 同步减少 hash[s[i]] 的值（保持频次准确）；
- 收缩过程直到窗口无冗余字符（hash[s[i]]），确保窗口是 “当前右边界下的最小有效窗口”。
步骤 4：更新最小窗口
只有当 count==tLen（窗口覆盖 t 所有字符）时，才判断当前窗口是否是最小的：
- 若当前窗口长度 j-i+1 小于 minLen，则更新 minLen 和 subLeft；
- 这里无需担心后续会有更小的窗口：因为收缩过程已保证当前窗口是 “最小有效”，后续右指针继续扩张时，会优先收缩冗余，再判断是否更新。
四、时间 / 空间复杂度分析
1. 时间复杂度：\(O(n)\)（\(n\) 是 s 的长度）
- 右指针 j 遍历 s 一次（\(O(n)\)）；
- 左指针 i 最多收缩 n 次（每个字符最多被移除一次，\(O(n)\)）；
- 总操作次数为 \(O(n) + O(n) = O(n)\)，属于线性时间，效率远超暴力枚举。
2. 空间复杂度：\(O(1)\)
- 哈希表是固定长度的数组（128 个元素），与输入字符串长度无关；
- 其他变量（count、minLen 等）均为常数级空间；
- 因此空间复杂度为常数级 \(O(1)\)。
五、实战技巧与避坑指南
1. 常见错误点
- 忘记 count 的作用，直接比对哈希表所有元素是否 ≥0：会导致时间复杂度升高（\(O(128n)\)），虽然仍是线性，但效率下降；
- 收缩窗口时未判断 `i 左指针超过右指针（无效窗口）；
- 初始 minLen 设为 s.length()：当 s 本身就是最小窗口时，会无法更新（应设为 s.length()+1）。
2. 同类题延伸（滑动窗口通用思路）
掌握本题的 “滑动窗口 + 哈希表” 框架后，可直接解决以下高频题：
- LeetCode 3：最长无重复子串：用哈希表记录字符最后出现位置，收缩窗口时直接跳到重复字符后；
- LeetCode 438：找到字符串中所有字母异位词：窗口长度固定为 t.length()，只需判断窗口内字符频次是否与 t 一致；
- LeetCode 567：字符串的排列：与 438 类似，窗口长度固定，判断是否是 t 的排列。
这些题的核心共性：用滑动窗口维护动态区间，用哈希表快速判断区间是否满足条件。
六、总结
“最小覆盖子串” 的解题关键的是：
- 用单哈希表同时记录字符需求和窗口频次，通过正负值简化判断；
- 滑动窗口的 “扩张 - 收缩” 逻辑：右指针找有效窗口，左指针优化最小窗口；
- 用 count 变量快速判断窗口是否覆盖 t 所有字符，避免冗余比对。
这道题的优化思路体现了算法设计的 “极致性”—— 用最少的空间、最低的时间复杂度解决问题。掌握后，你不仅能搞定这道题，更能举一反三，应对所有滑动窗口类问题。
如果在刷题过程中遇到其他疑问，或想深入探讨滑动窗口的更多应用场景，欢迎在评论区交流！
)
