2026/9/5大约 4 分钟
最小覆盖子串——滑动窗口
一、题目
给定字符串 s 和 t，找出 s 中包含 t 所有字符的最短子串。
例如：
s = "ADOBECODEBANC"
t = "ABC"答案：
"BANC"因为 "BANC" 中包含：
A → 1 个
B → 1 个
C → 1 个并且它是满足条件的最短子串。
二、核心思路
这道题使用：
滑动窗口 + 字符计数
维护一个窗口：
[left ........ right]其中：
right → 不断向右扩大窗口
left → 窗口满足要求后向右缩小目标是：
在满足条件的情况下，让窗口尽可能短。
三、两个计数数组
int cnt_t[128] = {};
int cnt_s[128] = {};cnt_t
表示：
字符串
t需要什么。
例如：
t = "ABC"那么：
cnt_t['A'] = 1
cnt_t['B'] = 1
cnt_t['C'] = 1cnt_s
表示：
当前窗口里有什么。
例如当前窗口：
"ADOBEC"那么：
cnt_s['A'] = 1
cnt_s['B'] = 1
cnt_s['C'] = 1四、什么叫“覆盖”？
只需要判断：
当前窗口里的数量 >= t 要求的数量例如：
t = "AABC"要求：
A → 2
B → 1
C → 1如果当前窗口：
"AABBC"那么：
A → 2 >= 2 ✅
B → 2 >= 1 ✅
C → 1 >= 1 ✅所以窗口合法。
注意：
窗口中的字符可以比
t更多。
只要至少满足 t 的要求即可。
五、滑动过程
例如：
s = "ADOBECODEBANC"
t = "ABC"right 不断向右走：
A
AD
ADO
ADOB
ADOBE
ADOBEC此时窗口：
"ADOBEC"已经包含：
A、B、C所以窗口合法。
合法以后怎么办？
目标是：
最短。
所以开始移动 left：
[ADOBEC]
↑
left移走 A：
[DOBEC]此时：
A → 0不满足要求。
于是停止缩小。
接下来继续移动 right。
后面再次满足
继续扩大窗口，最终找到：
"ADOBECODEBA"窗口合法。
继续移动 left：
DOBECODEBA
OBECODEBA
BECODEBA
ECODEBA
...最后得到：
"BANC"此时：
A → 1
B → 1
C → 1满足要求，而且不能再缩。
因此答案就是：
"BANC"六、代码
#include <string.h>
#include <limits.h>
bool is_covered(int cnt_s[], int cnt_t[])
{
// cnt_s：当前窗口拥有的字符数量
// cnt_t：题目要求的字符数量
//
// 只要有任意字符：
// 当前数量 < 要求数量
// 就说明窗口不满足条件
for (int i = 'A'; i <= 'Z'; i++)
{
if (cnt_s[i] < cnt_t[i])
return false;
}
for (int i = 'a'; i <= 'z'; i++)
{
if (cnt_s[i] < cnt_t[i])
return false;
}
return true;
}
char* minWindow(char* s, char* t)
{
// cnt_t：t 中每个字符需要多少个
int cnt_t[128] = {};
// cnt_s：当前滑动窗口中每个字符有多少个
int cnt_s[128] = {};
// 统计 t 的字符需求
for (int i = 0; t[i]; i++)
{
cnt_t[(unsigned char)t[i]]++;
}
// 当前答案的左右端点
int ans_left = -1;
int ans_right = INT_MAX / 2;
int left = 0;
// right 不断扩大窗口
for (int right = 0; s[right]; right++)
{
// s[right] 进入窗口
cnt_s[(unsigned char)s[right]]++;
// 只要窗口满足要求，就不断缩小
while (is_covered(cnt_s, cnt_t))
{
// 当前窗口合法
// 如果比之前的答案更短，就更新答案
if (right - left < ans_right - ans_left)
{
ans_left = left;
ans_right = right;
}
// s[left] 移出窗口
cnt_s[(unsigned char)s[left]]--;
// 左边界右移
left++;
}
}
// 没找到符合要求的子串
if (ans_left < 0)
return "";
// 将答案右边截断
s[ans_right + 1] = '\0';
// 返回答案起始位置
return s + ans_left;
}七、最关键的代码
整道题真正需要抓住的就是：
cnt_s[s[right]]++;表示：
右边界字符进入窗口。
然后：
while (is_covered(cnt_s, cnt_t))表示：
只要窗口已经满足要求，就开始缩。
缩窗口：
cnt_s[s[left]]--;
left++;表示：
把左边字符移出去，左边界向右移动。
八、这道题和 LeetCode 3 的区别
之前做过：
LeetCode 3：无重复字符的最长子串
它的逻辑是：
right 扩大
↓
出现重复
↓
left 缩小目标：
尽可能长而本题 76：
right 扩大
↓
窗口满足要求
↓
left 缩小
↓
直到不满足目标：
尽可能短所以可以记成：
3：不合法 → 缩
76：合法 → 缩九、整个算法
right 不断向右移动
↓
字符进入窗口
↓
窗口满足要求了吗？
↓
没有
↓
right 继续扩大
满足
↓
更新最短答案
↓
left 向右移动
↓
字符移出窗口
↓
重新判断是否满足
↓
直到不满足
↓
right 继续扩大十、复杂度
left 和 right 都只向右移动。
因此整体窗口移动次数是线性的。
当前 is_covered() 会遍历固定的 ASCII 字符范围 128，属于常数。
所以可以看作：
时间复杂度：O(n)
空间复杂度：O(1)十一、一句话记忆
cnt_t：我需要什么
cnt_s：我现在有什么
right：扩大窗口
left：缩小窗口
窗口满足要求：
记录答案 + 缩小
窗口不满足要求：
继续扩大最小覆盖子串 = 滑动窗口 + 字符计数 + 满足后尽可能缩小。
