通过字典 & 双指针滑动窗口实现

  • 时间复杂度：O (m + n)

  • 空间复杂度：O (k)

    1. function minWindow(s, t) {
    2.   let p1 = 0;
    3.   let p2 = 0;
    5.   const need = new Map();
    6.   for (const item of t) {
    7.       need.set(item, need.get(item) ? need.get(item) + 1 : 1);
    8.   }
    10.   let needType = need.size;
    12.   let res = '';
    14.   while (p2 < s.length) {
    15.       const item = s[p2];
    17.       if (need.has(item)) {
    18.           need.set(item, need.get(item) - 1);
    19.           if (need.get(item) === 0) needType--;
    20.       }
    22.       while (needType === 0) {
    23.           const newRes = s.substring(p1, p2 + 1);
    25.           if (!res || newRes.length < res.length) res = newRes;
    27.           const item2 = s[p1];
    29.           if (need.has(item2)) {
    30.               need.set(item2, need.get(item2) + 1);
    31.               if (need.get(item2) === 1) needType++;
    32.           }
    34.           p1++;
    35.       }
    37.       p2++;
    38.   }
    40.   return res;
    41. }

代码中的第一个循环是遍历了 t 进行了存储操作，所以时间复杂度是O (m)，在下面还有一个嵌套循环，但是嵌套的内部循环并不是遍历 s ，所以时间复杂度不算是O (n ^ 2)，按整体实现的功能来算是O (n)。

最后总结出来代码的时间复杂度为O (m + n) 其中 m 代表 t 的长度，n 代表 s 的长度。代码中主要存在 need 的集合，用来存储 t 字符串中不重复的字符，所以空间复杂度为O (k) 其中 k 代表字符串 t 中不重复字符的个数。