Problem:76. 最小覆盖子串
题目描述
给定两个字符串 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.length
- n == t.length
- 1 <= m, n <= 10^5
- s 和 t 由英文字母组成
核心思路:滑动窗口
解决滑动窗口类问题，核心在于想清楚以下 三个关键问题。只要这三个问题逻辑清晰，代码就能一气呵成。
Q1：什么时候扩大窗口？(Right 指针移动)
通常使用 r 指针作为循环的主动力，一直向右移动直到触达字符串末尾。
- 目的： 寻找 可行解。即通过不断纳入新字符，直到窗口内的字符能够覆盖 t 中的所有要求。
Q2：什么时候缩小窗口？(Left 指针移动)
这是寻找 最优解 的关键步骤。
- 时机：一旦窗口内的字符满足了 t 的要求（找到了一个可行解），我们就暂停 r 的移动，转而开始移动 l 指针收缩窗口。
- 目的：通过踢出左边的字符，尝试在保持“满足条件”的前提下，让窗口尽可能变小，从而更新最小长度。直到窗口不再满足条件，才重新去移动 r。
Q3：扩大和缩小时，如何维护数据状态？
3. 扩大和缩小时如何处理滑动窗口？
第一步：定义数据结构 我们需要两个哈希表来维护状态：
-
unordered_map<char,int> need：记录目标子串 t 中包含的字母及其需要的个数（Key 为字母，Value 为个数）。
-
unordered_map<char,int> win：记录当前滑动窗口中已包含的字母及其个数。
第二步：扩大窗口与计数维护 (r++)
随着右指针 r 的不断移动，我们将字符加入窗口。这里有一个关键的优化逻辑：只关注 need 中存在的字符。
-
当字符进入窗口时，若该字符在 need 中，将其加入 win。
-
计数器 cnt 的妙用：我们用 cnt 记录有多少种字符的数量已经达标。
- 判断条件：仅当 win[c] == need[c] 时，说明字符 c 的数量刚刚满足要求，此时执行 cnt++。
第三步：寻找可行解与缩小窗口 (l++)
-
判断可行解： 当 cnt == need.size() 时，意味着窗口内所有关键字符的数量都已达标，此时窗口中已经包含了一个可行解。
-
收缩窗口： 此时开始移动左指针 l，尝试剔除左侧字符以寻找更优（更短）的解。逻辑与扩大窗口同理（对称操作）。
第四步：结果记录的优化（关键点）
在循环中频繁截取字符串（s.substr）会有巨大的性能开销。因此，我们采用只记录索引的策略：
-
定义 start = 0 和 len = INT_MAX（初始化为极大值，方便后续更新最小值）。
-
在判断出更优解时，只更新 len 和 start 这两个数值。
-
最终输出：直到所有循环结束后，再执行一次 ans = s.substr(start, len) 截取最终结果。
class Solution {
public:
string minWindow(string s, string t) {
int n = s.size();
int m = t.size();
string ans;
int start = 0,len = INT_MAX;
unordered_map<char,int> win,need;
for(auto c : t) need[c]++;
int l = 0,r = 0;
int cnt = 0;
while(r < n) {
char c = s[r++];
if(need.count(c)) {
win[c]++;
if(win[c] == need[c]) cnt++;
}
while(cnt == need.size()) {
if(r – l > 0 && r – l < len) {
len = r – l;
start = l;
}
char d = s[l++];
if(need.count(d)) {
if(win[d] == need[d]) cnt—;
win[d]—;
}
}
}
if(len != INT_MAX) ans = s.substr(start,len);
return ans;
}
};
⏱️ 时间复杂度：
O
(
M
+
N
)
O(M + N)
O(M+N)
-
N 为字符串 t 的长度，M 为字符串 s 的长度。
-
虽然代码有双重循环，但 l 和 r 指针都只会从头走到尾一次，因此是线性的。
另外由于滑动窗口是用双指针来维护的，我的滑动窗口的代码风格是和双指针的写法比较像也比较统一，这种统一的模板写法更有利于我们进行套用，下面这几道都是滑动窗口的题目，大家可以参考一下我的写法。 【力扣Problem:3. 无重复字符的最长子串】滑动窗口移动策略详解 【438. 找到字符串中所有字母异位词】两种写法写滑动窗口 【力扣Problem: 239. 滑动窗口最大值】从multiset到大根堆与单调队列，三种方法处理滑动窗口最大值 这套写法来源于这里
❤️ 最后
新人up，如有不足还请多多指正，欢迎交流！ 如果内容对你有帮助的话，还请点赞支持一下喽🙏🙏 你的支持是我前进的最大动力！！ up正在更新力扣hot100的题目，有需要的朋友欢迎点赞、收藏加关注哦！
