1、题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 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.lengthn == t.length1 <= m, n <= 105s和t由英文字母组成
进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？
2、题解
- 使用滑动窗口（Sliding-window）
- 右侧移动直到包含所有子串为止
- 由于题目隐含的要求是”连续的子串“，所以不存在中间断开的多个串的情况，所以左侧向右移动的过程中可以很好的排除冗余的字符（其实就是排除连续的冗余的字符）
- “子字符串中该字符数量必须不少于
t中该字符数量“->这意味着允许：子串中某个字符的数量>=t中该字符的数量 - 左侧指针直到子串刚好不能包含所有t的字符为止，此时可知上一个下标到右侧指针处为最小子串
- 如此循环，最后对比子串长度，给出最短子串
- map.size是需要符合字符的个数，而一个字符想要符合检查条件 1、字符出现 2、字符出现满足额定个数。
while循环内置：
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>最小子串</title>
</head>
<body>
<script>
var minWindow = function (s, t) {
let left = 0;
let right = 0;
let len = s.length || 0;
let map = new Map(); //标准
let runTimeMap = new Map(); //运行时
let passCharNum = 0; //通过检查的char
let result = { left: 0, right: Infinity };
//map中收集检查标准
[...t].forEach((char) => {
// map.get(char) ? map.set(char, (map.get(char))++) : map.set(char, 0);
map.set(char, (map.get(char) || 0) + 1);
});
for (; right < len; right++) {
const currentChar = s[right];
//如果检查到一个key word
if (map.has(currentChar)) {
//为map中对应字段加1
runTimeMap.set(currentChar, (runTimeMap.get(currentChar) || 0) + 1);
//字符数量和类型皆匹配passCharNum+1(“子字符串中该字符数量必须不少于 t 中该字符数量“->这意味着允许：子串中某个字符的数量>=t中该字符的数量)
if (runTimeMap.get(currentChar) === map.get(currentChar)) {
//过了及格线就不记录了
passCharNum++;
}
}
//当所有字符的检查都通过了
if (passCharNum === map.size) {
let runTimeShortLen = right - left;
if (runTimeShortLen < result.right - result.left) {
result = { left, right };
}
//left指针右移（缩圈）
while (left < right) {
left++;
const loseChar = s[left - 1];
if (runTimeMap.has(loseChar)) {
if (runTimeMap.get(loseChar) - 1 < map.get(loseChar)) {
runTimeShortLen = right - (left - 1);
if (runTimeShortLen < result.right - result.left) {
result = { left: left - 1, right };
}
}
const losedCharRuntimeNum = runTimeMap.get(loseChar) - 1;
runTimeMap.set(loseChar, losedCharRuntimeNum);
if (runTimeMap.get(loseChar) < map.get(loseChar)) {
passCharNum--;
break;
}
} else {
runTimeShortLen = right - left;
if (runTimeShortLen < result.right - result.left) {
result = { left, right };
}
}
}
}
}
return result.right === Infinity
? ""
: s.slice(result.left, result.right + 1);
};
console.log(minWindow((s = "ab"), (t = "b")));
</script>
</body>
</html>
上面的实现方案中： if (passCharNum === map.size) {}内部包含了一个while循环的写法，这种写法if条件过多，重复代码太多。这个时候可以考虑while循环外置。
var minWindow = function (s, t) {
let left = 0;
let right = 0;
let len = s.length || 0;
let map = new Map(); //标准
let runTimeMap = new Map(); //运行时
let passCharNum = 0; //通过检查的char
let result = { left: 0, right: Infinity };
//map中收集检查标准
[...t].forEach((char) => {
// map.get(char) ? map.set(char, (map.get(char))++) : map.set(char, 0);
map.set(char, (map.get(char) || 0) + 1);
});
for (; right < len; right++) {
const currentChar = s[right];
//如果检查到一个key word
if (map.has(currentChar)) {
//为map中对应字段加1
runTimeMap.set(currentChar, (runTimeMap.get(currentChar) || 0) + 1);
//字符数量和类型皆匹配passCharNum+1(“子字符串中该字符数量必须不少于 t 中该字符数量“->这意味着允许：子串中某个字符的数量>=t中该字符的数量)
if (runTimeMap.get(currentChar) === map.get(currentChar)) {
//仅过了及格线时记录，超过及格线的情况不计入passCharNum
passCharNum++;
}
}
//当right右移到符map标准时，就应该开始不断地缩圈（left右移）试探最小的子串
while (passCharNum === map.size) {
if (result.right - result.left > right - left) {
result = { left, right };
}
const loseChar = s[left];
if (runTimeMap.has(loseChar)) {
runTimeMap.set(loseChar, runTimeMap.get(loseChar) - 1);
if (runTimeMap.get(loseChar) < map.get(loseChar)) {
passCharNum--;
}
}
left++;
}
}
return result.right === Infinity
? ""
: s.slice(result.left, result.right + 1);
};
