题解 | #最小覆盖子串#

先思考一下暴力法

• 以 S = 'aaat'， T = 't' 为例：
• [l : r] 表示一个子串。如下图， 时， 有 4 个选择； 时， 有 3 个选择； 时， 有 2 个选择 ……以此类推
  
• 可见暴力穷举也是在使用双指针去扫描，只是双指针的移动没有外加一些约束。会出现 指针对字符符的重复扫描，做了很多重复的工作。

窗口的扩张

• [l : r]看作一个窗口，右指针右移，是为了纳入目标字符，先找到可行解——即纳入了所有目标字符。
• 在还没找齐目标字符之前，左指针不动。因为如果此时它右移，可能丢失现有的目标字符。
• 什么时候停止扩张窗口？——当前窗口包含了所有目标字符。
• 此时再纳入字符，条件依然满足，但徒增子串长度。此时应该优化可行解：收缩窗口，左指针右移。

窗口的收缩

• 保持条件满足的前提下，收缩窗口是优化可行解。当窗口不再包含所有目标字符，即有目标字符丢失，就不再收缩。
• 此时应该扩张窗口，补充目标字符。
• 为了找到最优解，一直在做这两种操作中的一个，直到窗口的右端到达边界。

总结滑动窗口套路

1. 先找到一个可行解，再优化这个可行解。
2. 优化到不能优化，产生出一个可能的最优解。
3. 继续找新的可行解，再优化这个可行解。
   ……
4. 在所有可能的最优解中，比较出最优解。

窗口的扩张或收缩的标识

• 我们知道，窗口扩张 or 收缩取决于——当前窗口是否包含了所有目标字符。
• 定义一个 missingType 变量，表示当前缺失的字符种类数。
• 它的初始值是源字符串的字符种类数。为 0 表示没有缺少任何种类，找齐了所有目标字符。

missingType 取决于 各个字符的缺失情况

• 用一个哈希表，去存各个目标字符和对应的缺失个数。
• 比如输入字符串为 'baac'，则 map 初始为 { a: 2, b: 1, c: 1 }，这些值是动态的，比如窗口新纳入一个 a，则 map["a"] 减 1。map["a"] 为 0 代表不缺 a 了，a 字符找齐了。

代码 JavaScript

var minWindow = function(S, T) {
  let minLen = S.length + 1;
  let start = S.length;     // 结果子串的起始位置
  let map = {};             // 存储目标字符和对应的缺失个数
  let missingType = 0;      // 当前缺失的字符种类数
  for (const c of T) {      // t为baac的话，map为{a:2,b:1,c:1}
    if (!map[c]) {
      missingType++;        // 需要找齐的种类数 +1
      map[c] = 1;
    } else {
      map[c]++;
    }
  }
  let l = 0, r = 0;                // 左右指针
  for (; r < S.length; r++) {      // 主旋律扩张窗口，超出s串就结束
    let rightChar = S[r];          // 获取right指向的新字符
    if (map[rightChar] !== undefined) map[rightChar]--; // 是目标字符，它的缺失个数-1
    if (map[rightChar] == 0) missingType--;   // 它的缺失个数新变为0，缺失的种类数就-1
    while (missingType == 0) {                // 当前窗口包含所有字符的前提下，尽量收缩窗口
      if (r - l + 1 < minLen) {    // 窗口宽度如果比minLen小，就更新minLen
        minLen = r - l + 1;
        start = l;                 // 更新最小窗口的起点
      }
      let leftChar = S[l];          // 左指针要右移，左指针指向的字符要被丢弃
      if (map[leftChar] !== undefined) map[leftChar]++; // 被舍弃的是目标字符，缺失个数+1
      if (map[leftChar] > 0) missingType++;      // 如果缺失个数新变为>0，缺失的种类+1
      l++;                          // 左指针要右移 收缩窗口
    }
  }
  if (start == S.length) return "";
  return S.substring(start, start + minLen); // 根据起点和minLen截取子串
};

感谢阅读