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

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

function findAnagrms(s, p) {
  // 声明 need 为我们需要的字符个数 窗口为空对象
  let need = {},
    window = {};

  // 用 字符串 p 初始化 need, 要考虑重复情况
  [...p].map((c) => (need[c] ? need[c]++ : (need[c] = 1)));

  // 窗口指针的初始化为 0 是一个左闭右开的区间 [left, right)  valid 用来记录窗口中已经满足条件的字符个数 res 记录满足条件的数组下标值
  let left = 0,
    right = 0,
    valid = 0,
    res = [];
  let keysLength = Object.keys(need).length;

  // 开始滑动
  while (right < s.length) {
    // c 为进入窗口的字符
    let c = s[right];
    right++;

    // 窗口数据更新 如果 c 是满足要求的字符
    if (need[c]) {
      // 更新窗口中的数据
      window[c] ? window[c]++ : (window[c] = 1);
      // 如果窗口中的字符与需要的字符数量相等
      if (window[c] === need[c]) {
        // 计数加一
        valid++;
      }
    }

    // 判断左侧窗口是否需要收缩
    while (right - left >= p.length) {
      // 如果 window 已经满足 need  那么需要起始索引加入 res
      if (valid === keysLength) {
        res.push(left);
      }

      // d 是即将要移出的元素
      let d = s[left];
      left++;
      // 进行窗口的一系列更新
      if (need[d]) {
        if (window[d] === need[d]) {
          valid--;
        }
        window[d]--;
      }
    }
  }

  return res;
}