企业官网建设流程全解析

一、 题目描述（题目链接）

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的最短窗口子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。

示例：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

二、 核心思路：滑动窗口

这道题要求我们在一个长字符串 s 中寻找一个满足特定条件的连续子串，并且要求这个子串尽可能短。面对这种“连续子区间”的最优化问题，滑动窗口是最佳的解题范式。

滑动窗口的核心在于维护两个指针 left 和 right，通过不断调整窗口的大小来寻找最优解：

寻找可行解（右指针扩张）：right 指针不断向右移动，扩大窗口，直到窗口内的字符能够覆盖字符串 t 的所有字符。

优化可行解（左指针收缩）：当窗口满足条件时，left 指针开始向右移动，缩小窗口。在收缩的过程中，如果窗口依然满足条件，我们就记录下当前窗口的长度，并尝试寻找更短的解。

循环往复：当窗口不再满足条件时，right 继续向右移动，寻找下一个满足条件的窗口。

三、 算法实现细节

为了实现上述思路，我们需要解决几个关键问题：

如何判断窗口包含了t的所有字符？

1. 使用两个哈希表（由于字符集是 ASCII，可以直接使用大小为 128 的数组代替哈希表）：need 记录 t 中字符的需求量，window 记录当前窗口内字符的数量。
2. 引入变量 valid，记录当前窗口中已经满足数量要求的字符种类数。
3. 当 valid == required（t 中不同字符的种类数）时，说明窗口已完全覆盖 t。

如何更新最短子串？

使用 start 和 len 变量，分别记录最短子串的起始索引和长度。每次窗口满足条件时，检查当前长度 right - left 是否小于 len，若小于则更新。

四、 C++ 完整代码

class Solution { public: string minWindow(string s, string t) { // 记录 t 中每个字符的需求量 vector<int> need(128, 0); // 记录当前窗口中每个字符的数量 vector<int> window(128, 0); // 统计 t 的字符需求 (传统 for 循环) for (int i = 0; i < t.size(); i++) { need[t[i]]++; } // 计算 t 中不同字符的种类数 (关键步骤) int required = 0; for (int i = 0; i < 128; i++) { if (need[i] > 0) { required++; } } int left = 0, right = 0; int valid = 0; // 记录 window 中已经满足 need 条件的字符种类数 int start = 0, len = INT_MAX; // 记录最小覆盖子串的起始位置和长度 while (right < s.size()) { char c = s[right]; right++; // 扩大窗口：处理 s[right] if (need[c] > 0) { window[c]++; // 如果当前窗口中该字符的数量达到了 t 中的需求 if (window[c] == need[c]) { valid++; } } // 收缩窗口：当窗口已经覆盖了 t 中所有字符时 while (valid == required) { // 注意：这里必须用 required，不能用 need.size()！ // 更新最小覆盖子串 if (right - left < len) { start = left; len = right - left; } // 处理 s[left]，准备收缩 char d = s[left]; left++; if (need[d] > 0) { // 移出窗口的字符会导致窗口不再满足条件 if (window[d] == need[d]) { valid--; } window[d]--; } } } return len == INT_MAX ? "" : s.substr(start, len); } };

五、 复杂度分析

时间复杂度：O(m + n)。其中 m 是字符串 s 的长度，n 是字符串 t 的长度。虽然代码中有一个嵌套的 while 循环，但 left 和 right 指针都只会从左到右遍历一遍 s，因此内层循环的总执行次数最多为 O(m)。

空间复杂度：O(1)。由于字符集的大小是固定的（这里使用 128 大小的数组），因此所需的空间是常数级别的。