LeetCode 最小覆盖子串 滑动窗口题解

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

这道题是滑动窗口里比较难的一道，难点不在框架而在「怎么判断窗口已经覆盖了 t」这个条件的维护上。

先明确两件事。一是「涵盖所有字符」要算重数：t 是 AABC 的话，窗口里必须有两个 A，只有一个不算覆盖。二是子串要求连续，且窗口内允许有 t 里没有的字符，只要该有的都有就行。

解题思路

框架是标准的双指针滑动窗口，但节奏跟「无重复字符的最长子串」那道相反。那道题是先扩窗，遇到冲突才缩窗，求的是最大值；这道题是不断扩窗直到满足条件，然后立刻尽力缩窗以求更短的解，求的是最小值。

所以两个指针的分工是：右指针负责扩大窗口去凑齐条件，一旦条件满足，左指针就开始往右压缩，压到条件被破坏为止，期间记录下最短的那个窗口。之后右指针继续前进，重复这个过程。

关键在于判断条件怎么高效维护。每次都重新统计窗口内的字符是 O(n) 的，整体就退化成 O(n^2)。这里用的技巧是拿一个计数表记录「还差多少」：

先把 t 里每个字符的需求量统计进 t_map。窗口右边进来一个字符，如果表里有它，就把需求量减一；窗口左边出去一个字符，需求量加一。这样表里的值就是「当前还缺几个」，负数表示有多余的。

然后再用一个 needType 记录「还有几种字符没凑够」。某个字符的需求量从 1 减到 0 的那一刻，说明这一种刚好凑齐，needType 减一；反过来从 0 加到 1，说明这一种又缺了，needType 加一。于是判断整个窗口是否覆盖 t，只需要看 needType 是否为零，是 O(1) 的。

这个「用一个计数器汇总多个条件」的手法是这类题的通用套路，值得记住。

题解

var minWindow = function (s, t) {
  let right = 0;
  let left = 0;
  const t_map = new Map();

  for (item of t) {
    t_map.set(item, t_map.has(item) ? t_map.get(item) + 1 : 1);
  }

  let needType = t_map.size;

  let res = '';
  while (right < s.length) {
    const s_val = s[right];

    if (t_map.has(s_val)) {
      t_map.set(s_val, t_map.get(s_val) - 1);
      if (t_map.get(s_val) === 0) needType -= 1;
    }
    // 第一次进入到这里时，表示已经找到满足字符串长度的字符
    while (needType === 0) {
      let newRes = s.slice(left, right + 1);

      if (!res || newRes.length < res.length) res = newRes;
      const l_val = s[left];
      if (t_map.has(l_val)) {
        t_map.set(l_val, t_map.get(l_val) + 1);
        if (t_map.get(l_val) === 1) needType += 1;
      }
      // 开始减小字符串的长度
      left += 1;
    }
    right += 1;
  }

  return res;
};

几处细节值得单独说。

needType 初始化成 t_map.size 而不是 t.length，这是种类数不是字符数。t 为 AABC 时 size 是 3（A、B、C 三种），而重数信息保存在每个键对应的值里。这两个层次要分开，混了就错。

判断凑齐的条件严格用 === 0 而不是 <= 0。窗口里某个字符可能超量，比如需要一个 A 但窗口里有三个，此时需求量是 -2。只有从 1 变成 0 那一次才是「刚好凑齐」的转折点，用 <= 0 会在超量时重复扣减 needType，把它减成负数，判断就全乱了。同理左边释放时用 === 1 卡住「刚好变缺」那一刻。

if (!res || newRes.length < res.length) 里的 !res 是为了处理第一次找到解的情况——此时 res 是空字符串，长度为 0，任何候选都不会「更短」，所以必须靠这个条件先把第一个解收下。

内层 while (needType === 0) 是个循环而不是 if，这一点很关键。窗口满足条件后可能连续压缩好几位——比如窗口左边有一串 t 里不存在的字符，或者某个字符超量了，这些都可以直接甩掉。用 if 只压一次就跳出去了，得不到最小解。

最后返回 res，如果压根没找到覆盖子串，它保持初始的空字符串，正好符合题目要求。

• 时间复杂度：O(m + n) m 是 t 的长度，n 是 s 的长度

复杂度是线性的，理由是两个指针都只单向前进、各自最多走 n 步。虽然代码里有嵌套的 while，但内层循环推进的是 left，它在整个执行过程中总共也只会前进 n 次，不是每轮外层都重新走一遍，所以不是平方级。这是双指针类算法分析时的常见误判点。

• 空间复杂度：O(m)

空间只有那张计数表，最多存 t 中不同字符的种类数。字符集固定的话（比如只有大小写字母），这个值有常数上界，也可以视作 O(1)。