76. 最小覆盖子串 🟥
题目
leetcode 困难
题目
给定两个字符串 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。
题解
哈希表 + 滑动窗口
- 时间复杂度：O(N)（更准确地说是 O(|S| + |T|)）
字符串
t遍历一次用来建need表。
字符串s遍历时，右指针right从头走到尾（N 次），左指针left也最多从头走到尾（N 次）。嵌套在while里的内部循环总共执行次数不会超过 N 次，因此总时间是线性的 O(N)。 - 空间复杂度：O(Σ)
Σ 表示字符集的大小（如果是 ASCII 码，最多存 128 个键值对）。因为我们只用了一个
need对象来存储t中的字符及其数量，所以空间复杂度可以认为是 O(1) 或 O(128) 常数级别。
js
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function (s, t) {
// 1. 初始化购物清单 (哈希表)
const need = {}
for (let char of t) {
need[char] = (need[char] || 0) + 1
}
let missing = t.length // 记录总共还【差】多少个必需字符
let left = 0 // 窗口左边界
let right = 0 // 窗口右边界
let minLen = Infinity // 记录历史最小窗口的长度
let start = 0 // 记录历史最小窗口的起始位置
// 2. 右指针开始逛超市，扩大窗口
while (right < s.length) {
let charRight = s[right]
console.log('♻️ charRight:', charRight)
console.log('need:', need, 'missing:', missing)
// 如果遇到的字符在清单上
if (need[charRight] !== undefined) {
// 并且我们当前确实还需要这个字符 (需求量 > 0)
if (need[charRight] > 0) {
missing-- // 必需品数量 -1
}
// 无论如何，把清单上的需求量 -1
// (如果是多拿的，需求量会变成负数，代表"溢出/冗余")
need[charRight]--
}
right++ // 右指针继续前进
console.log('need:', need, 'missing:', missing)
// 3. 当 missing === 0，说明买齐了，左指针开始精简退货，缩小窗口
while (missing === 0) {
console.log('missing === 0，左指针开始缩小窗口')
// 更新最小窗口记录
if (right - left < minLen) {
minLen = right - left
start = left
}
let charLeft = s[left]
console.log('left:', left, 'charLeft:', charLeft)
// 看看准备扔掉的字符，是不是清单上的
if (need[charLeft] !== undefined) {
// 因为要扔掉了，所以需求量要被加回来
need[charLeft]++
// 如果需求量加回来后 > 0，说明此时这个字符变得"紧缺"了
if (need[charLeft] > 0) {
missing++ // 必需品丢失，达不到要求了，打破循环
}
}
left++ // 左指针向右移动，把最前面的字符扔掉
console.log('need:', need, 'missing:', missing)
}
}
// 4. 返回结果
return minLen === Infinity ? '' : s.substring(start, start + minLen)
}
console.log('🌰', minWindow('ADOBECODEBANC', 'ABC')) // 输出："BANC"
console.log('-------------')
console.log('🌰', minWindow('ABAACBAB', 'ABC')) // 输出："BANC"
console.log('-------------')
console.log('🌰', minWindow('a', 'a')) // 输出："a"
console.log('-------------')
console.log('🌰', minWindow('a', 'aa')) // 输出:""执行结果
♻️ charRight: A
need: { A: 1, B: 1, C: 1 } missing: 3
need: { A: 0, B: 1, C: 1 } missing: 2
♻️ charRight: D
need: { A: 0, B: 1, C: 1 } missing: 2
need: { A: 0, B: 1, C: 1 } missing: 2
♻️ charRight: O
need: { A: 0, B: 1, C: 1 } missing: 2
need: { A: 0, B: 1, C: 1 } missing: 2
♻️ charRight: B
need: { A: 0, B: 1, C: 1 } missing: 2
need: { A: 0, B: 0, C: 1 } missing: 1
♻️ charRight: E
need: { A: 0, B: 0, C: 1 } missing: 1
need: { A: 0, B: 0, C: 1 } missing: 1
♻️ charRight: C
need: { A: 0, B: 0, C: 1 } missing: 1
need: { A: 0, B: 0, C: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 0 charLeft: A
need: { A: 1, B: 0, C: 0 } missing: 1
♻️ charRight: O
need: { A: 1, B: 0, C: 0 } missing: 1
need: { A: 1, B: 0, C: 0 } missing: 1
♻️ charRight: D
need: { A: 1, B: 0, C: 0 } missing: 1
need: { A: 1, B: 0, C: 0 } missing: 1
♻️ charRight: E
need: { A: 1, B: 0, C: 0 } missing: 1
need: { A: 1, B: 0, C: 0 } missing: 1
♻️ charRight: B
need: { A: 1, B: 0, C: 0 } missing: 1
need: { A: 1, B: -1, C: 0 } missing: 1
♻️ charRight: A
need: { A: 1, B: -1, C: 0 } missing: 1
need: { A: 0, B: -1, C: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 1 charLeft: D
need: { A: 0, B: -1, C: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 2 charLeft: O
need: { A: 0, B: -1, C: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 3 charLeft: B
need: { A: 0, B: 0, C: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 4 charLeft: E
need: { A: 0, B: 0, C: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 5 charLeft: C
need: { A: 0, B: 0, C: 1 } missing: 1
♻️ charRight: N
need: { A: 0, B: 0, C: 1 } missing: 1
need: { A: 0, B: 0, C: 1 } missing: 1
♻️ charRight: C
need: { A: 0, B: 0, C: 1 } missing: 1
need: { A: 0, B: 0, C: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 6 charLeft: O
need: { A: 0, B: 0, C: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 7 charLeft: D
need: { A: 0, B: 0, C: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 8 charLeft: E
need: { A: 0, B: 0, C: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 9 charLeft: B
need: { A: 0, B: 1, C: 0 } missing: 1
🌰 BANC
-------------
♻️ charRight: A
need: { A: 1, B: 1, C: 1 } missing: 3
need: { A: 0, B: 1, C: 1 } missing: 2
♻️ charRight: B
need: { A: 0, B: 1, C: 1 } missing: 2
need: { A: 0, B: 0, C: 1 } missing: 1
♻️ charRight: A
need: { A: 0, B: 0, C: 1 } missing: 1
need: { A: -1, B: 0, C: 1 } missing: 1
♻️ charRight: A
need: { A: -1, B: 0, C: 1 } missing: 1
need: { A: -2, B: 0, C: 1 } missing: 1
♻️ charRight: C
need: { A: -2, B: 0, C: 1 } missing: 1
need: { A: -2, B: 0, C: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 0 charLeft: A
need: { A: -1, B: 0, C: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 1 charLeft: B
need: { A: -1, B: 1, C: 0 } missing: 1
♻️ charRight: B
need: { A: -1, B: 1, C: 0 } missing: 1
need: { A: -1, B: 0, C: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 2 charLeft: A
need: { A: 0, B: 0, C: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 3 charLeft: A
need: { A: 1, B: 0, C: 0 } missing: 1
♻️ charRight: A
need: { A: 1, B: 0, C: 0 } missing: 1
need: { A: 0, B: 0, C: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 4 charLeft: C
need: { A: 0, B: 0, C: 1 } missing: 1
♻️ charRight: B
need: { A: 0, B: 0, C: 1 } missing: 1
need: { A: 0, B: -1, C: 1 } missing: 1
🌰 ACB
-------------
♻️ charRight: a
need: { a: 1 } missing: 1
need: { a: 0 } missing: 0
missing === 0，左指针开始缩小窗口
left: 0 charLeft: a
need: { a: 1 } missing: 1
🌰 a
-------------
♻️ charRight: a
need: { a: 2 } missing: 2
need: { a: 1 } missing: 1
🌰