给定两个字符串 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。
又是一道困难题，这题做了一个半小时才做出来，一开始只考虑对比，没想到频率。后面终于茅塞顿开，才勉强写出来
1. 算法核心思想：状态机流转与延迟截取
通过双指针（front 与 rear）维护一个大小可变的滑动窗口，利用“有效需求计数器”（valid）将字符串匹配问题抽象为状态机模型。
- 状态控制：引入
valid变量表示“尚未凑齐的字符总数”。通过valid > 0（饥饿）与valid == 0（吃饱）两种状态的交替，精确控制左右指针的移动时机，避免了高昂的数组全量对比开销。 - 双映射记账：利用
unordered_map快速验证字符是否属于目标集，利用定长数组note和note2结合大小写 ASCII 偏移量，精确记录目标字符频率与当前窗口字符频率。 - 延迟截取（内存优化）：在寻找全局最小子串的过程中，放弃直接使用
substr开辟新内存，转而使用minmark数组记录历史最优解的起始与终止坐标，最后统一截取，从根源上杜绝了内存溢出。
2. 宏观运行机制
程序的生命周期在两个嵌套的内部 while 循环中交替进行：
- 阶段一：右指针扩张（吸收状态） 当
valid > 0时，系统处于未满足状态。右指针rear步进，读取字符。若该字符在目标集合中，系统计算其对应的数组映射索引mark，并将其加入当前窗口记录note2中。若加入后该字符的总量未超过目标需求量note，则记为一次有效收集，valid减 1。满足valid == 0的瞬间，记录当前窗口坐标。 - 阶段二：左指针收缩（排异状态） 当
valid == 0达成，右指针停止，左指针front启动。系统尝试通过前移front来剔除多余字符以缩短窗口长度。若被剔除的字符属于目标集合，且剔除后其频率低于了目标下限，则破坏了覆盖条件，valid递增。在每次合法剔除后，动态更新全局最优的minmark坐标组合。随后循环退回阶段一，直至遍历完整个字符串。
class 最小覆盖子串 {
public:
string minWindow(string s, string t) {
vector<int> note = vector<int>(26*2, 0);
vector<int> note2 = vector<int>(26*2, 0);
unordered_map<char, int> map;
for (auto c : t) {
map[c]++;
if ('a' <= c && c <= 'z') {
note[c - 'a']++;
}
else {
note[c - 'A' + 26]++;
}
}
int len = 0;
int minLen = INT_MAX;
string minRes = "";
int front = 0;
int rear = 0;
int valid = t.size();
int minmark[] = {0,0};
while (rear < s.size()) {
//首先先吃
while (rear < s.size() && valid > 0) {//循环到吃饱为止
int char1 = s[rear];
if (map.find(char1) != map.end()) {//如果在map里面，需要判断清单是否满足，会增饱
int mark;
if ('a' <= char1 && char1 <= 'z') {
note2[char1 - 'a']++;
mark = char1 - 'a';
}
else {
note2[char1 - 'A' + 26]++;
mark = char1 - 'A' + 26;
}
//刚刚吃完和note对比看看有没有完成清单
if (note2[mark] <= note[mark]) {
valid--;
}
}
//不在map里面，直接吃，但是不增饱
len++;
rear++;
//清单为0的时候开始截取
if (valid == 0) {
if (minLen > len) {
minLen = len;
minmark[0] = front;
minmark[1] = rear;
}
}
}
//front开始吐
while (front < rear && valid == 0) {
if (map.find(s[front]) != map.end()) {//当前的在清单里面
int char1 = s[front];//对应的note2变化，现在note2少了一个必然不相等，那就得移动右指针
int mark;
if ('a' <= char1 && char1 <= 'z') {
note2[char1 - 'a']--;
mark = char1 - 'a';
}
else {
note2[char1 - 'A' + 26]--;
mark = char1 - 'A' + 26;
}
if (note2[mark] < note[mark]) {
valid++;//吐完了清单也空了
}
}
front++;//不管吐了什么，反正一定会前移
len--;
if (valid == 0) {
if (minLen > len) {
minLen = len;
minmark[0] = front;
minmark[1] = rear;
}
}
}
}
return minRes = s.substr(minmark[0], minmark[1] - minmark[0]);
}
};
3. 复杂度剖析
- 时间复杂度：O(N+M)。其中 N 为字符串
s的长度，M 为字符串t的长度。虽然存在内外嵌套的while循环，但front和rear指针均不回退，最多分别遍历字符串一次。数组索引偏移计算与状态判定均为 O(1) 时间开销。 - 空间复杂度：O(Σ)。系统额外开辟了两个长度为 52 的定长数组和一个
unordered_map用于记录目标集字符频次。其空间占用与目标字符串的字符种类数相关联，上限为常数级别，内存开销低。