双指针专题(七)：覆盖所有需求的最小代价——「最小覆盖子串」-程序员充电站

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

力扣 76. 最小覆盖子串

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

题目分析：

输入：字符串s(资源池), 字符串t(需求清单)。
目标：在s中找到一个最短的子串，包含t中所有的字符（包括重复字符，比如t="AA", 子串里也得有两个A）。
输出：这个最短子串。如果不存在，返回空字符串。

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

一直扩：窗口一直向右，直到变成ADOBEC。此时包含了 A, B, C。这是一个可行解，但太长了。
尝试缩：左边A移出去？不行，A 也是必须的。
继续跑：...直到找到BANC，包含 A, B, C，且长度只有 4。

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

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

needMap：记录t中每个字符需要多少个。 (比如A:1, B:1, C:1)
windowMap：记录当前窗口里已经有多少个字符。
valid变量：记录有多少个字符已经**“达标”**了。
- 比如t需要A1个。当窗口里A的数量从 0 变成 1 时，valid++。
- 当valid等于need.size时，说明所有种类的字符都凑齐了！

操作逻辑：

进窗口 (right)：
- 读字符，更新windowMap。
- 如果window[c] === need[c]，说明这个字符凑够了，valid++。
收缩窗口 (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); };