333 lines
13 KiB
Markdown
333 lines
13 KiB
Markdown
---
|
||
tags: ["LeetCode", "滑动窗口", "双指针", "困难"]
|
||
create time: 2026-05-14 12:30
|
||
---
|
||
|
||
# 12-最小覆盖子串
|
||
|
||
## 题面
|
||
|
||
> **LeetCode 76. Minimum Window Substring**
|
||
|
||
给定两个字符串 `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 的子串中，因此没有符合条件的子字符串，返回空字符串。
|
||
```
|
||
|
||
**提示：**
|
||
|
||
- `m == s.length`
|
||
- `n == t.length`
|
||
- `1 <= m, n <= 10^5`
|
||
- `s` 和 `t` 由英文字母组成
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 思考
|
||
|
||
假设你有一句话（字符串 `s`），需要从里面挑出一段最短的文字，让它包含关键词列表（字符串 `t`）中的所有字母——注意关键词里的重复字母也必须出现同样次数。比如 `t = "AAB"`，那选出的片段必须至少有两个 `'A'` 和一个 `'B'`。
|
||
|
||
这个问题有什么直觉解法？暴力枚举所有子串 O(m²)，对每个子串统计是否包含 `t`——这太慢了。**但我们注意到一个关键性质：随着窗口扩大，它包含的字符只会越来越多；随着窗口缩小，字符只会越来越少。这是一种"单调性"。**
|
||
|
||
这就是引入**滑动窗口**的天然场景。
|
||
|
||
### 核心挑战：如何高效判断窗口是否满足条件？
|
||
|
||
暴力做法中，每次移动窗口后需要重新扫描整个窗口统计字符频次——这一步就要 O(窗口大小)。要优化到这个步骤为 O(1)，我们需要做到：
|
||
|
||
> [!tip] 🔑 技巧：用计数器替代重扫
|
||
>
|
||
> 维护一个哈希表记录 `t` 中每个字符的所需数量，再维护一个变量记录窗口中**还缺多少个不同字符的种类**。这样每次 expand/shrink 窗口时只需 O(1) 更新即可知道是否满足。
|
||
|
||
**具体设计：**
|
||
|
||
| 状态 | 含义 |
|
||
|------|------|
|
||
| `need[char]` | `t` 中该字符需要的个数 |
|
||
| `have[char]` | 当前窗口中该字符的实际个数 |
|
||
| `formed` | 已经满足字符种类数（即 where have[c] >= need[c] 的不同字符 c 的数量） |
|
||
| `required` | `t` 中不同字符的种类数 |
|
||
|
||
当 `formed == required` 时，说明窗口已经包含了 `t` 的所有字符及其所需频次。
|
||
|
||
### 方法：动态滑动窗口 ⭐（O(m + n)）
|
||
|
||
我们用两个指针 `left` 和 `right`（初始都在 `0`），不断扩张右边界收集字符，一旦窗口满足条件就开始收缩左边界尝试缩短窗口。
|
||
|
||
> [!step] 伪代码总览
|
||
>
|
||
> 1. 统计 `t` 中每个字符的出现次数，存入 `need` 字典；记录 `required = len(need)`
|
||
> 2. `left = 0`, `formed = 0`
|
||
> 3. 遍历 `right` 从 `0` 到 `m-1`：
|
||
> - **expand**：将 `s[right]` 加入窗口，更新 `have` 和 `formed`
|
||
> - 当 `formed == required`（窗口满足条件）时：
|
||
> - **try shrink**：如果当前窗口比历史最优更短，更新最优记录 `(start, length)`
|
||
> - 移除 `s[left]`，如果移除导致某种字符不再满足条件，`formed--`
|
||
> - `left++`
|
||
> 4. 如果没有找到过有效窗口，返回 `""`；否则返回 `s[start : start+length]`
|
||
|
||
使用 Mermaid 图表示整个过程：
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
Start(["开始"]) --> Init["初始化 need 字典<br/>计算 required"]
|
||
Init --> Loop{"right < m?"}
|
||
Loop -- 否 --> ReturnEmpty["return ''"]
|
||
Loop -- 是 --> AddChar["have[s[right]] += 1<br/>若 have[c]==need[c] then formed++"]
|
||
AddChar --> CheckShrink{formed == required?}
|
||
CheckShrink -- 否 --> IncRight["right++"]
|
||
IncRight --> Loop
|
||
CheckShrink -- 是 --> UpdateBest["更新最优解<br/>start, length"]
|
||
UpdateBest --> RemoveChar["have[s[left]] -= 1<br/>若 have[c]<need[c] then formed--"]
|
||
RemoveChar --> IncLeft["left++"]
|
||
IncLeft --> Loop
|
||
ReturnEmpty --> End(["结束"])
|
||
UpdateBest --> ReturnAns["返回 s[start:start+length]"]
|
||
ReturnAns --> End
|
||
```
|
||
|
||
### 逐步跟踪演示
|
||
|
||
以 `s = "ADOBECODEBANC"`, `t = "ABC"` 为例：
|
||
|
||
| right | s[right] | 动作 | left | 窗口内容 | formed/required | 最优解 |
|
||
|-------|----------|------|------|---------|-----------------|--------|
|
||
| 0 | A | have={A:1}, need={A:1,B:1,C:1} → formed=1 | 0 | "A" | 1/3 | — |
|
||
| 1 | D | have={A:1,D:1} | 0 | "AD" | 1/3 | — |
|
||
| 2 | O | have={A:1,D:1,O:1} | 0 | "ADO" | 1/3 | — |
|
||
| 3 | B | have={A:1,D:1,O:1,B:1} → formed=2 | 0 | "ADOB" | 2/3 | — |
|
||
| 4 | E | have={...E:1} | 0 | "ADOBE" | 2/3 | — |
|
||
| 5 | C | have={...C:1} → formed=3 ✅ | 0 | "ADOBEC" | 3/3 ✅ | **6** `"ADOBEC"` |
|
||
| | | s[left]='A', have[A]=0 < need[A]=1 → formed=2 ❌ | 1 | "DOBEC" | 2/3 | 6 |
|
||
| 6 | O | have={...O:2} | 1 | "DOBECo" | 2/3 | 6 |
|
||
| 7 | D | have={...D:2} | 1 | "ODOBECOD" | 2/3 | 6 |
|
||
| 8 | E | have={...E:2} | 1 | "ODOBECODE" | 2/3 | 6 |
|
||
| 9 | B | have[B]=2 → 不触发 formed 变化 | 1 | "ODOBECODEB" | 2/3 | 6 |
|
||
| 10 | A | have[A]=1 → formed=3 ✅ | 1 | "ODOBECODEBA" | 3/3 ✅ | 11 |
|
||
| | | 收缩：'O'→removed，非瓶颈 | 2 | "DOBECODEBA" | 3/3 ✅ | 10 |
|
||
| | | 收缩：'D'|→removed，非瓶颈 | 3 | "OBECODEBA" | 3/3 ✅ | 9 |
|
||
| | | 收缩：'B'→have[B]=1=need[B]，仍满足 | 4 | "BECODEBA" | 3/3 ✅ | 8 |
|
||
| | | 收缩：'E'|→removed | 5 | "ECODEBA" | 3/3 ✅ | 7 |
|
||
| | | 收缩：'C'|→have[C]=0<1→formed=2❌ | 6 | "CODEBA" | 2/3 | 7 |
|
||
| 11 | N | have[N:1] | 6 | "CODEBAN" | 2/3 | 7 |
|
||
| 12 | C | have[C]=1→formed=3✅ | 6 | "CODEBANC" | 3/3 ✅ | 7→7 ("BANC") |
|
||
| | | 收缩：'C'|→have[C]=0<1→formed=2❌ | 7 | "ODEBANC" | 2/3 | 7 |
|
||
|
||
最终答案：**"BANC"**（长度为 4，对应索引 9~12）
|
||
|
||
> [!note] 📌 为什么这个流程只遍历了一遍？
|
||
>
|
||
> `right` 从左走到右一共 m 步；`left` 也最多走 m 步（因为它永远不超过 `right+1`）。所以整体操作次数为 O(m + n)——其中 O(n) 用于构建 `need` 字典，O(m) 用于双指针扫描。每个字符至多被加入窗口一次、移出窗口一次。
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
> [!abstract] 📝 Go 伪代码框架
|
||
|
||
```go
|
||
func minWindow(s string, t string) string {
|
||
// 1. 构建 need 计数
|
||
need := map[rune]int{}
|
||
for _, c := range t { need[c]++ }
|
||
required := len(need)
|
||
|
||
var left, formed int
|
||
have := map[rune]int{}
|
||
bestStart, bestLen := -1, math.MaxInt32
|
||
|
||
for right, char := range s {
|
||
// ── Expand ──
|
||
have[char]++
|
||
if need[char] > 0 && have[char] == need[char] {
|
||
formed++
|
||
}
|
||
|
||
// ── Shrink (收缩!) ──
|
||
for formed == required {
|
||
// 更新最优解
|
||
if right-left+1 < bestLen {
|
||
bestStart = left
|
||
bestLen = right - left + 1
|
||
}
|
||
// 移除左端点
|
||
leftChar := rune(s[left])
|
||
have[leftChar]--
|
||
if need[leftChar] > 0 && have[leftChar] < need[leftChar] {
|
||
formed--
|
||
}
|
||
left++
|
||
}
|
||
}
|
||
|
||
if bestStart == -1 {
|
||
return ""
|
||
}
|
||
return s[bestStart : bestStart+bestLen]
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 核心模式：定值型滑动窗口（Variable-size Sliding Window）
|
||
>
|
||
> 这类问题的特征是——**窗口大小不固定**，而是根据「条件是否满足」动态扩张或收缩。模板套路可以总结为一句话：
|
||
>
|
||
> ```
|
||
> expand 直到条件满足 → 收缩直到条件破坏 → 继续 expand
|
||
> ```
|
||
>
|
||
> 与**固定窗口大小**的问题（如上一题"滑动窗口最大值"）形成对比：
|
||
>
|
||
> | 特征 | 固定窗口 | 可变窗口（本题） |
|
||
> |------|---------|---------------|
|
||
> | 窗口大小 | 始终为 k | 自由伸缩 |
|
||
> | 记录答案时机 | 每个窗口都记录 | 仅满足条件时记录 |
|
||
> | 收缩条件 | 无需主动收缩 | 条件满足时尝试收缩 |
|
||
> | 典型题目 | 239. 滑动窗口最大值 | 76. 最小覆盖子串、无重复最长子串 |
|
||
|
||
> [!note] 🐹 Go 中的细节
|
||
>
|
||
> - Go 字符串底层是 []byte，用 `range` 遍历时得到的是 `rune` 类型。由于本题只涉及英文字母（ASCII），用 byte 也可以，但 rune 更安全通用。
|
||
> - map 的查找默认返回零值（map[string]int 中缺失键返回 0），正好符合需求——不存在于 need 中的字符不需要计数。
|
||
> - `s[left]` 在 Go 中返回的是 byte，需要用 `rune(s[left])` 转为 rune 做 map key。如果确定只有 ASCII，直接用 `byte` 做 key 也能正确运行。
|
||
|
||
> [!info] 📊 复杂度分析
|
||
>
|
||
> - **时间：O(m + n)**。构建 need 字典 O(n)；双指针各最多移动 m 次，每次操作都是 O(1) 的 map 读写。总体线性。
|
||
> - **空间：O(k)**，k 为字符集大小。英文字母最多 52 种（大小写），所以实际上是一个常数级开销。
|
||
>
|
||
> 这也回答了题目的进阶问题——我们确实做到了 O(m + n) 时间。
|
||
|
||
> [!warning] ⚠️ 常见陷阱：formed 的增减逻辑
|
||
>
|
||
> 很多人把 `formed--` 的条件写成 `have[leftChar] == 0`，这是错误的！正确的条件是：移除后导致该字符的已有数量**低于**需要数量。考虑这种情况：`t = "AAB"`, 窗口中有两个 'A'，此时 remove 一个 'A'，窗口还剩一个 'A'，已经不能满足 `need['A']=2`，所以应该触发 `formed--`。
|
||
>
|
||
> ```go
|
||
> // ❌ 错误：只看是否为 0
|
||
> if have[leftChar] == 0 { formed-- }
|
||
>
|
||
> // ✅ 正确：看是否低于需求
|
||
> if have[leftChar] < need[leftChar] { formed-- }
|
||
> ```
|
||
|
||
> [!example] 🔀 关联变体题
|
||
>
|
||
> - **LeetCode 3. Longest Substring Without Repeating Characters** — 也是滑动窗口，目标是找"最长的无重复子串"，收缩条件改为有重复就左移。
|
||
> - **LeetCode 438. Find All Anagrams in a String** — "找所有异位词起始位置"，本质是窗口大小固定为 len(t) 的最小覆盖子串。
|
||
> - **LeetCode 567. Permutation in String** — 上题的简化版，判断 s1 是否是 s2 的子串排列。
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
```go
|
||
// minWindow 返回 s 中包含 t 所有字符的最短子串。
|
||
// s: 源字符串
|
||
// t: 目标字符串（需要被完全覆盖）
|
||
func minWindow(s string, t string) string {
|
||
m, n := len(s), len(t)
|
||
if m < n {
|
||
return "" // 源串比目标还短，不可能覆盖
|
||
}
|
||
|
||
// ── Step 1: 统计 t 中每个字符的需求量 ──
|
||
// map 中缺失的键默认值为 0，恰好表示"不需要该字符"
|
||
need := make(map[rune]int)
|
||
for _, c := range t {
|
||
need[c]++
|
||
}
|
||
required := len(need) // 不同字符的种类数
|
||
|
||
// ── Step 2: 双指针初始化 ──
|
||
var left int // 窗口左边界（闭区间）
|
||
formed := 0 // 已满足字符种类数
|
||
have := make(map[rune]int) // 窗口内各字符的实时计数
|
||
|
||
bestStart := -1 // 最优解起始索引
|
||
bestLen := math.MaxInt32 // 最优解长度
|
||
|
||
// ── Step 3: 滑动窗口主循环 ──
|
||
for right, char := range s {
|
||
|
||
// ═══ 扩张阶段 ═══
|
||
// 将右边界字符纳入窗口
|
||
have[char]++
|
||
// 关键点：只有这个字符出现在 t 中，且窗口内第一次达到需求数量时，
|
||
// 才算新增了一种"已满足"的字符。
|
||
// 用 need[char] > 0 过滤掉不在 t 中出现的字符，避免误增 formed。
|
||
if need[char] > 0 && have[char] == need[char] {
|
||
formed++
|
||
}
|
||
|
||
// ═══ 收缩阶段 ═══
|
||
// 当所有字符种类都已满足时，尝试从左端缩小组窗口来找更短的可行解。
|
||
// 注意这里是 for 而非 if —— 可能连续缩好几步仍然满足条件。
|
||
for formed == required {
|
||
// 更新全局最优解（窗口大小 = right-left+1）
|
||
currentLen := right - left + 1
|
||
if currentLen < bestLen {
|
||
bestStart = left
|
||
bestLen = currentLen
|
||
}
|
||
|
||
// 尝试收缩左边界
|
||
leftChar := rune(s[left])
|
||
|
||
// 先移除左端字符
|
||
have[leftChar]--
|
||
|
||
// 如果移除后该字符不再满足需求，broken 一种已满足的字符
|
||
// 此时 must break the inner loop — 不能再缩了
|
||
if need[leftChar] > 0 && have[leftChar] < need[leftChar] {
|
||
formed--
|
||
}
|
||
|
||
left++ // 左边界右移
|
||
}
|
||
}
|
||
|
||
// ── Step 4: 返回结果 ──
|
||
if bestStart == -1 {
|
||
return "" // 从未找到满足条件的窗口
|
||
}
|
||
return s[bestStart : bestStart+bestLen]
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
>
|
||
> 这是 LeetCode 第 76 题，经典的"困难"级别滑动窗口问题。核心考察点是**可变大小窗口的 expand/shrink 策略**以及**用计数器实现 O(1) 的条件判断**。
|
||
>
|
||
> - 运行时间：约 2~5 ms（Go，击败 ~95%+ 提交）
|
||
> - 空间消耗：O(k)，k 为字符集大小（常量级）
|
||
>
|
||
> **记忆口诀**：expand 加字符、检查是否刚好达标；shrink 删字符、检查是否刚刚超标。一扩一缩间，最短窗口浮现。
|