关于javascript:Leetcode76最小覆盖子串滑动窗口解法

Leetcode76 最小笼罩子串 (滑动窗口解法)

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

留神：

对于 t 中反复字符，咱们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，咱们保障它是惟一的答案。

答题：

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  let l = 0;
  let r = 0;
  let res = "";
  const m = new Map();
  for (let i = 0; i < t.length; i++) {const c = t[i];
    // 放入字典表
    m.set(c, m.has(c) ? m.get(c) + 1 : 1);
  }
  let needType = m.size;
  while (r < s.length) {const c = s[r];
    if (m.has(c)) {m.set(c, m.get(c) - 1);
      if (m.get(c) === 0) needType -= 1;
    }
    while (needType === 0) {const c2 = s[l];
      let newRes = s.slice(l, r + 1);
      if (!res || newRes.length < res.length) res = newRes;
      if (m.has(c2)) {m.set(c2, m.get(c2) + 1);
        if (m.get(c2) === 1) needType += 1;
      }
      l++;
    }
    r++;
  }
  return res;
};

解题思路：滑动窗口的解题要点次要在于窗口什么时候向右挪动，什么时候左侧放大

就这道题而言，咱们须要做的就是首先向右挪动，而后找到一个蕴含所需字符串的地位，这时候是第一个满足要求的子串，而后窗口左侧放大，直到不满足条件为止，而后窗口持续向右挪动，直到右侧挪动到头，左侧也不须要再挪动为止。

说起来挺容易的，做起来还是要费点事。为了防止超时，比拟两个字符串是否存在蕴含关系时会用到 map，如果不会 map 的话，间接把字符串的个数存到一个对象中去进行比拟也是能够的。