LeetCode 最小覆盖子串 题解分析

一、题目描述

给你两个字符串 s 和 t，长度分别为 m 和 n。请你找出 s 中的 最短窗口子串，该子串需要包含 t 中的所有字符（含重复字符）。如果不存在符合条件的子串，返回空字符串 ""，题目测试用例保证答案唯一。

核心要求：

• 覆盖 t 中所有字符，包含重复次数（例如t="AAB"，窗口必须至少包含 2 个 A、1 个 B）；
• 在所有合法窗口中，选取长度最小的子串；
• 无合法子串则返回空。

二、解题算法：滑动窗口（双指针）

1. 算法选型原因

本题是经典的字符串子串匹配最优解问题，暴力枚举所有子串的时间复杂度为 O(n²)，效率极低。而**滑动窗口（双指针）**可以将时间复杂度优化至 O(m+n)，是该题型的标准最优解法。

滑动窗口核心思想：右指针扩张窗口，满足条件后左指针收缩窗口，动态维护最小合法窗口。

2. 核心思路拆解

步骤1：统计目标字符串字符需求

通过哈希表 need 统计字符串 t 中每个字符的出现次数，记录窗口需要满足的字符数量要求。同时统计 t 中不同字符的种类数required，作为窗口合法的判定基准。

步骤2：双指针遍历字符串 s（扩张窗口）

定义右指针 right 遍历整个字符串 s，逐个将字符纳入窗口：

• 若当前字符是 t 中需要的字符，将哈希表中对应字符的需求数减一；
• 当某字符的需求数减为 0 时，说明窗口内该字符的数量已完全满足 t 的需求，更新已满足需求的字符种类数 matched。

步骤3：收缩窗口，寻找最小长度

当 matched == required 时，说明当前窗口已完全覆盖t 的所有字符，为合法窗口。此时尝试收缩左边界，寻找更短的合法窗口：

• 每次更新当前最小窗口的长度和起始位置；
• 左指针移出窗口的字符若为目标字符，需恢复其需求计数；
• 若移出后该字符需求不再为 0，说明窗口不再满足条件，终止收缩，继续扩张右指针。

步骤4：结果判定

遍历结束后，若未找到任何合法窗口，返回空字符串；否则根据记录的起始位置和最小长度，截取结果子串返回。

三、代码逐行详解

class Solution {
 public:
     string minWindow(string s, string t) {
         // 边界判空，直接返回空串
         if (s.empty() || t.empty()) return "";
​
         // 哈希表：存储t中每个字符需要的数量
         unordered_map<char, int> need;
         for (char c : t) need[c]++;
​
         // t中不同字符的总种类数
         const int required = need.size();
         // 窗口内已满足数量要求的字符种类数
         int matched = 0;
​
         // 滑动窗口左右指针、最小窗口长度、结果起始位置
         int left = 0, min_len = INT_MAX, start = 0;
​
         // 右指针遍历s，扩张窗口
         for (int right = 0; right < (int) s.size(); ++right) {
             char c = s[right];
             // 当前字符是目标字符，更新需求计数
             if (need.count(c)) {
                 need[c]--;
                 // 该字符数量完全满足要求，匹配种类+1
                 if (need[c] == 0) matched++;
             }
​
             // 窗口完全合法，尝试收缩左边界优化最小长度
             while (matched == required) {
                 // 更新最小窗口
                 if (right - left + 1 < min_len) {
                     min_len = right - left + 1;
                     start = left;
                 }
​
                 // 左指针移出窗口的字符
                 char out = s[left];
                 // 移出的是目标字符，恢复计数
                 if (need.count(out)) {
                     // 移出前刚好满足，移出后不再满足，匹配种类-1
                     if (need[out] == 0) matched--;
                     need[out]++;
                 }
                 // 左指针右移，收缩窗口
                 left++;
             }
         }
         // 无合法窗口返回空，否则截取最小窗口子串
         return min_len == INT_MAX ? "" : s.substr(start, min_len);
     }
 };

关键变量说明

• need：需求哈希表，记录 t 各字符所需数量，数值可负（负数表示窗口内该字符数量冗余）；
• required：t 不重复字符总数，窗口合法的判定标准；
• matched：窗口内已达标字符种类数，等于 required 时窗口合法；
• min_len：记录合法窗口的最小长度，初始为极大值；
• start：记录最小窗口的起始下标，用于最终截取子串。

四、复杂度分析

1. 时间复杂度：O(m + n)

m 为字符串 s 长度，n 为字符串 t 长度。

• 遍历 t 统计字符需求：O(n)；
• 双指针遍历 s：左右指针均只会从头到尾遍历一次，总次数为 O(m)；
• 哈希表增删改查为常数时间 O(1)。

整体时间复杂度为线性 O(m+n)，效率最优。

2. 空间复杂度：O(1)

字符为 ASCII 字符，哈希表 need 最多存储 128 个字符，空间开销为常数，与输入字符串长度无关，故空间复杂度为 O(1)。

五、核心解题要点

1. 冗余字符处理：哈希表数值可为负数，代表窗口内该字符数量超过 t 需求，不影响窗口合法性，仅当数值从 0 变为正数时，才会破坏窗口合法性；
2. 先合法再收缩：必须等待窗口完全满足条件后再收缩，保证每一次收缩都是为了寻找更优解；
3. 边界兜底：初始最小长度设为极大值，遍历结束后判断是否更新过，避免无合法子串的情况报错；
4. 种类匹配而非数量匹配：通过 matched 统计达标字符种类，避免每次遍历哈希表判断窗口合法性，大幅优化效率。

‍