中等

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

*思路

  1. 首先遍历目标串 t , 记录种类数missingType，和种类的对应个数 map
  2. 然后遍历 s ，移动 r 指针，利用-1来确定种类数和个数符合条件。
  3. 若missingType=0 , 说明子串符合条件，这个时候移动 l 指针，利用+1 来缩小范围。
  4. 若 l 指针的移动，导致子串缺少目标种类了，着继续移动 r 指针。以此循环
  1.   let s = "ADOBECODEBANC", t = "ABC"
  2.   var minWindow = function (s, t) {
  3.     let minLen = s.length + 1;
  4.     let start = s.length;     // 结果子串的起始位置
  5.     let map = {};             // 存储目标字符和对应的缺失个数
  6.     let missingType = 0;      // 当前缺失的字符种类数
  7.     for (const c of t) {      // t为baac的话，map为{a:2,b:1,c:1}
  8.       if (!map[c]) {
  9.         missingType++;        // 需要找齐的种类数 +1
  10.         map[c] = 1;
  11.       } else {
  12.         map[c]++;
  13.       }
  14.     }
  15.     let l = 0, r = 0;                // 左右指针
  16.     for (; r < s.length; r++) {      // 扩张窗口，超出s串就结束
  17.       let rightChar = s[r];          // 获取right指向的新字符
  18.       if (map[rightChar] !== undefined) map[rightChar]--; // 是目标字符，它的缺失个数-1
  19.       if (map[rightChar] == 0) missingType--;   // 它的缺失个数新变为0，缺失的种类数就-1
  20.       console.log('R->', map, r, '个数' + missingType);
  21.       while (missingType == 0) {                // 当前窗口包含所有字符
  22.         if (r - l + 1 < minLen) {    // 每一次都符合条件，比较子串长度，保存最短的。
  23.           minLen = r - l + 1;
  24.           start = l;
  25.         }
  26.         console.log('完成', l, r);
  27.         let leftChar = s[l];          // 左指针要右移，左指针指向的字符要被丢弃
  28.         if (map[leftChar] !== undefined) map[leftChar]++; // 被舍弃的是目标字符，缺失个数+1
  29.         if (map[leftChar] > 0) missingType++;      // 如果缺失个数新变为>0，缺失的种类+1
  30.         l++;                          // 左指针要右移 收缩窗口
  31.         console.log('L---', map, l, '个数' + missingType);
  32.       }
  33.     }
  34.     if (start == s.length) return "";
  35.     return s.substring(start, start + minLen); // 根据起点和minLen截取子串
  37.   };