Leetcode76最小覆蓋子串(滑動(dòng)窗口解法)

給你一個(gè)字符串 s 、一個(gè)字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 "" 。

注意：

對(duì)于 t 中重復(fù)字符，我們尋找的子字符串中該字符數(shù)量必須不少于 t 中該字符數(shù)量。
如果 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;
};

解題思路：滑動(dòng)窗口的解題要點(diǎn)主要在于窗口什么時(shí)候向右移動(dòng)，什么時(shí)候左側(cè)縮小

就這道題而言，我們需要做的就是首先向右移動(dòng)，然后找到一個(gè)包含所需字符串的位置，這時(shí)候是第一個(gè)滿足要求的子串，然后窗口左側(cè)縮小，直到不滿足條件為止，然后窗口繼續(xù)向右移動(dòng)，直到右側(cè)移動(dòng)到頭，左側(cè)也不需要再移動(dòng)為止。

說起來挺容易的，做起來還是要費(fèi)點(diǎn)事。為了避免超時(shí)，比較兩個(gè)字符串是否存在包含關(guān)系時(shí)會(huì)用到map，如果不會(huì)map的話，直接把字符串的個(gè)數(shù)存到一個(gè)對(duì)象中去進(jìn)行比較也是可以的。