76. 最小覆盖子串
4 min
题目
解法：滑动窗口
思路
核心思想是使用滑动窗口配合字符计数数组动态维护覆盖状态。
正确性在于：当右指针扩展窗口时，通过need数组精确追踪每个字符的覆盖缺口；当窗口满足条件时，左指针收缩过程中通过need[d]>0判断是否破坏覆盖条件，确保每次收缩都找到当前右边界下的最小窗口。
- Step 1: 初始化need数组记录t字符需求，need_count记录剩余需匹配字符数
- Step 2: 右指针移动时更新字符计数，当need_count归零触发窗口收缩
- Step 3: 左指针收缩时更新最小窗口，并通过need[d]>0判断覆盖条件破坏点
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
string minWindow(string s, string t) {
// ASCII 字符计数数组
vector<int> need(128, 0);
for (char c : t) need[c]++;
int need_count = t.size(); // 总共还需要匹配的字符数量
int left = 0, right = 0;
int min_len = INT_MAX;
int start = 0;
while (right < s.size()) {
// 1. 进窗口逻辑
char c = s[right];
// 如果当前字符是 t 需要的（计数大于0），则有效匹配数减1
if (need[c] > 0) {
need_count--;
}
// 无论是不是需要的字符，都减1
// 如果是无关字符，会变成负数；如果是多余的某个所需字符，也会变成负数或0
need[c]--;
right++;
// 2. 窗口收缩逻辑（当所有字符都找齐了）
while (need_count == 0) {
class Solution {
public:
string minWindow(string s, string t) {
// ASCII 字符计数数组
vector<int> need(128, 0);
for (char c : t) need[c]++;
int need_count = t.size(); // 总共还需要匹配的字符数量
int left = 0, right = 0;
int min_len = INT_MAX;
int start = 0;
while (right < s.size()) {
// 1. 进窗口逻辑
char c = s[right];
// 如果当前字符是 t 需要的（计数大于0），则有效匹配数减1
if (need[c] > 0) {
need_count--;
}
// 无论是不是需要的字符，都减1
// 如果是无关字符，会变成负数；如果是多余的某个所需字符，也会变成负数或0
need[c]--;
right++;
// 2. 窗口收缩逻辑（当所有字符都找齐了）
while (need_count == 0) {
// 更新最小覆盖子串结果
if (right - left < min_len) {
min_len = right - left;
start = left;
}
// 尝试移出左边界字符
char d = s[left];
need[d]++; //把之前的减法补回来
// 如果补回来之后 > 0，说明刚才移除的是一个“必须且不富余”的字符
// 于是窗口变得不再满足条件，需要重新去右边找
if (need[d] > 0) {
need_count++;
}
left++;
}
}
return min_len == INT_MAX ? "" : s.substr(start, min_len);
}
};