企业官网建设流程全解析

这道题是Hard级别，也是无数面试者的噩梦。 前面的题（水果成篮、无重复子串）都是窗口**“大了才缩”。 这道题反过来：窗口“不够大（没凑齐）就一直扩，一旦凑齐了就拼命缩”，试图找到最小**的那个解。

力扣 76. 最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring/

题目分析：

• 输入：字符串s(资源池), 字符串t(需求清单)。

• 目标：在s中找到一个最短的子串，包含t中所有的字符（包括重复字符，比如t="AA", 子串里也得有两个A）。

• 输出：这个最短子串。如果不存在，返回空字符串。

例子：s = "ADOBECODEBANC",t = "ABC"

1. 一直扩：窗口一直向右，直到变成ADOBEC。此时包含了 A, B, C。这是一个可行解，但太长了。

2. 尝试缩：左边A移出去？不行，A 也是必须的。

3. 继续跑：...直到找到BANC，包含 A, B, C，且长度只有 4。

核心思维：两个哈希表 + 有效计数器

这道题单纯用 Map 会比较乱，我们需要维护两个概念：

1. needMap：记录t中每个字符需要多少个。 (比如A:1, B:1, C:1)

2. windowMap：记录当前窗口里已经有多少个字符。

3. valid变量：记录有多少个字符已经**“达标”**了。

   • 比如t需要A1个。当窗口里A的数量从 0 变成 1 时，valid++。

   • 当valid等于need.size时，说明所有种类的字符都凑齐了！

操作逻辑：

1. 进窗口 (right)：

   • 读字符，更新windowMap。

   • 如果window[c] === need[c]，说明这个字符凑够了，valid++。

2. 收缩窗口 (left)：

   • While (valid === need.size)：只要凑齐了，就一直缩！

     • 更新结果：如果当前窗口更短，记录下来。

     • 踢出字符：把s[left]移出窗口。

     • 关键判断：如果移出的字符导致window[c] < need[c]，说明不再达标了，valid--。

     • left++。

代码实现 (JavaScript)

JavaScript

/** * @param {string} s * @param {string} t * @return {string} */ var minWindow = function(s, t) { // 1. 统计需求 t const need = new Map(); for (const c of t) { need.set(c, (need.get(c) || 0) + 1); } const window = new Map(); let left = 0, right = 0; let valid = 0; // 记录有多少种字符已经满足要求了 // 记录最小子串的起始位置和长度 let start = 0; let minLen = Infinity; while (right < s.length) { // --- 进窗口 --- const c = s[right]; right++; // 右指针移动 // 如果这个字符是我们需要关注的 if (need.has(c)) { window.set(c, (window.get(c) || 0) + 1); // 如果窗口里的数量刚刚好达到了需求，valid + 1 if (window.get(c) === need.get(c)) { valid++; } } // --- 出窗口 --- // 当 valid 等于 need 的大小时，说明所有字符都凑齐了 // 这时候开始尝试收缩左边界，寻找“最小” while (valid === need.size) { // 更新最小覆盖子串 if (right - left < minLen) { start = left; minLen = right - left; } // 准备移出左边的字符 const d = s[left]; left++; // 如果移出的字符是我们需要关注的 if (need.has(d)) { // 如果移出前，数量刚好达标。那移出后肯定就不达标了 if (window.get(d) === need.get(d)) { valid--; } window.set(d, window.get(d) - 1); } } } return minLen === Infinity ? "" : s.substr(start, minLen); };

深度辨析：为什么是window.get(c) === need.get(c)？

• 假设t = "AA",s = "AAAA"。

• need = {A: 2}。

• right读第一个 A:window={A:1}。不等于 2，valid 不变。

• right读第二个 A:window={A:2}。等于 2！valid++(A 达标了)。

• right读第三个 A:window={A:3}。不等于 2，valid 不变。

• 结论：valid只在“刚刚好满足”的那一瞬间增加。这保证了即使窗口里有 100 个 A，valid也只算一次。

总结

拿下这道题，不定长滑动窗口这一块你就彻底毕业了。 它的模板是所有滑动窗口里最全的：

1. Map 统计需求。

2. valid变量判断状态。

3. while(valid === target)进行收缩优化。