一、 题目描述题目链接给定两个字符串 s 和 t长度分别是 m 和 n返回 s 中的最短窗口子串使得该子串包含 t 中的每一个字符包括重复字符。如果没有这样的子串返回空字符串 。示例输入s ADOBECODEBANC, t ABC输出BANC二、 核心思路滑动窗口这道题要求我们在一个长字符串 s 中寻找一个满足特定条件的连续子串并且要求这个子串尽可能短。面对这种“连续子区间”的最优化问题滑动窗口是最佳的解题范式。滑动窗口的核心在于维护两个指针 left 和 right通过不断调整窗口的大小来寻找最优解寻找可行解右指针扩张right 指针不断向右移动扩大窗口直到窗口内的字符能够覆盖字符串 t 的所有字符。优化可行解左指针收缩当窗口满足条件时left 指针开始向右移动缩小窗口。在收缩的过程中如果窗口依然满足条件我们就记录下当前窗口的长度并尝试寻找更短的解。循环往复当窗口不再满足条件时right 继续向右移动寻找下一个满足条件的窗口。三、 算法实现细节为了实现上述思路我们需要解决几个关键问题如何判断窗口包含了t的所有字符使用两个哈希表由于字符集是 ASCII可以直接使用大小为 128 的数组代替哈希表need 记录 t 中字符的需求量window 记录当前窗口内字符的数量。引入变量 valid记录当前窗口中已经满足数量要求的字符种类数。当 valid requiredt 中不同字符的种类数时说明窗口已完全覆盖 t。如何更新最短子串使用 start 和 len 变量分别记录最短子串的起始索引和长度。每次窗口满足条件时检查当前长度 right - left 是否小于 len若小于则更新。四、 C 完整代码class Solution { public: string minWindow(string s, string t) { // 记录 t 中每个字符的需求量 vectorint need(128, 0); // 记录当前窗口中每个字符的数量 vectorint 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 大小的数组因此所需的空间是常数级别的。