1. // 76. 最小覆盖子串
    2. // 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
    4. //  
    6. // 注意：
    8. // 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
    9. // 如果 s 中存在这样的子串，我们保证它是唯一的答案。
    10. //  
    12. // 示例 1：
    14. // 输入：s = "ADOBECODEBANC", t = "ABC"
    15. // 输出："BANC"
    16. // 示例 2：
    18. // 输入：s = "a", t = "a"
    19. // 输出："a"
    20. // 示例 3:
    22. // 输入: s = "a", t = "aa"
    23. // 输出: ""
    24. // 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
    25. // 因此没有符合条件的子字符串，返回空字符串。
    27. /**
    28.  * @param {string} s
    29.  * @param {string} t
    30.  * @return {string}
    31.  */
    33. // 题解
    34. // 找出所有子串
    35. // 找出最短子串
    37. // 双指针维护一个滑动窗口
    38.  var minWindow = function(s, t) {
    39.     // 定义左右指针或者叫做快慢指针,起始都是从零开始的
    40.     let l = 0;
    41.     let r = 0;
    43.     // 创建一个集合用来存储t,键为item, 值为item出现的次数
    44.     let map = new Map();
    45.     for(let item of t) {
    46.         map.set(item, map.get(item) ? map.get(item) + 1 : 1)
    47.     }
    49.     let mapType = map.size;
    50.     let res = '';
    51.     // 遍历S
    52.     while(r < s.length) {
    53.         const c = s[r];
    55.         // 如果包含当前值，就更新map
    56.         if(map.has(c)) {
    57.             map.set(c, map.get(c) - 1);
    59.             // 什么时候停止呢？当map的value 小于等于0时，这里我们不用再去遍历
    60.             if(map.get(c) === 0) {
    61.                 mapType -= 1
    62.             }
    63.         }
    65.         // 左指针怎么移动,
    66.         // 左指针什么时候移动呢？就是当我们找到在S中找到了所有t,也就是mapType === 0的时候
    67.         while(mapType === 0) {
    69.             const newRes = s.substring(l, r+1);
    70.             if(!res || newRes.length < res.length) {
    71.                 res = newRes
    72.             }
    73.             // 获取左指针当前值
    74.             const c2 = s[l];
    76.             // 如果左指针存在于map中，给value + 1
    77.             if(map.has(c2)) {
    78.                 map.set(c2, map.get(c2) + 1);
    80.                 if(map.get(c2) === 1) {
    81.                     mapType += 1
    82.                 }
    83.             }
    85.             l += 1
    86.         }
    89.         r += 1;
    90.     }
    91.     return res
    92. };
    94. let s = "ADOBECODEBANC", t = "ABC";
    96. console.log(minWindow(s, t));

    时间复杂度：O（M + N) m 就是t的长度， n 就是s长度
    空间复杂度：新建了一个字典，最坏的情况就是t的长度, O(k) k就是t里面不同字符的个数