438-找到字符串中所有字母异位词.md

438-找到字符串中所有字母异位词

原题 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引

输入: s: "cbaebabacd" p: "abc"

输出: [0, 6]

解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

解题思路 need 是 p 字符串各个字符 key 和字符数量 value 的对象 win 是目前滑动窗口的字符和字符数的对像 len 是 p 的字符种类数量（比如：“aa”的 len 为 1） val 为窗口当前满足 need 的字符种类数量 __ 遍历 s 字符串 进入窗口的字符在 need 上，加 win 窗口的字符数量，直到等于该字符 need 的数量，给 val++ 出去窗口的字符在 need 上，减 win 窗口的字符数量，如果 win 减少之前满足 need，给 val-- 当 val === len，j+1 就是其中一个答案

（也可以只用 len 一个变量，方便理解就用多了 val）

代码

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
  const res = [],
    win = {},
    need = {},
    pLen = p.length;
  let len = 0,
    val = 0;
  for (const x of p) {
    if (need[x] === undefined) {
      need[x] = win[x] = 0;
      len++;
    }
    need[x]++;
  }
  for (let i = 0; i < s.length; i++) {
    const j = i - pLen;
    if (s[i] in need && ++win[s[i]] === need[s[i]]) val++;
    // 为什么 s[j] in need 的时候，win[s[j] 就要 --
    if (s[j] in need && win[s[j]]-- === need[s[j]]) val--;
    if (val === len) res.push(j + 1);
  }
  return res;
};

复杂度 时间复杂度：O(N) s 的长度 空间复杂度：O(1) 小写英文字符最多有 26 个，所以为常数

感觉还是使用滑动窗口的方式来解决更好 参考同类题目的解法 76-最小覆盖子串

const findAnagrams = function (s, t) {
  let res = [];
  let left = 0;
  let right = 0;
  let needs = {};
  let window = {};
  for (const c of t) {
    needs[c] ? needs[c]++ : (needs[c] = 1);
  }

  let match = 0;
  while (right < s.length) {
    // 这一段代码还是能看懂的，至少看一下s里面的字符串是否有匹配到t
    let c1 = s[right];
    if (needs[c1]) {
      window[c1] ? window[c1]++ : (window[c1] = 1);
      if (window[c1] == needs[c1]) {
        match++;
      }
    }
    right++;

    // 这里要开始计算left了，通过不断的 left++ 来收缩窗口
    while (right - left >= t.length) {
      if (match === Object.keys(needs).length) {
        res.push(left);
      }

      //  这里也是要计算，当 left++ 之后，会给 window / match 带来什么变化
      let c2 = s[left];
      if (needs[c2]) {
        window[c2]--;
        if (window[c2] < needs[c2]) {
          match--;
        }
      }

      left++;
    }
  }

  return res;
};