10、找到字符串中所有字母异位置词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

题目分析

1. 异位词可以理解成字符出现的次数相同，但是顺序不同，也就是排列组合的问题
2. 题目要求找到所有异位词的子串，也就是找到所有的排列组合

解题思路

1. 首先判断异常场景，如果字符串为空或者字符串长度小于异位词长度，直接返回空数组
2. 初始化左右指针，用于窗口滑动
3. 初始化存储异位词的数组
4. 初始化异位词基准串和窗口串
5. 遍历异位词，计算异位词中字符出现的次数
6. 初始化计数器，用于记录窗口中字符出现的次数
7. 窗口滑动，右指针小于字符串长度
8. 记录右指针字符出现的次数
9. 如果字符出现的次数和异位词中字符出现的次数相同，计数器+1

var findAnagrams = function (s, p) {
  const pLen = p.length;

  // 异常场景直接返回
  if (s.length == 0) return [];
  if (s.length < pLen) return [];

  // 窗口左右指针
  let left = 0;
  let right = 0;
  // 用于存储起始索引
  const indexList = [];
  // 异位字串基准串
  const needMap = new Map();
  // 记录窗口值
  const windowMap = new Map();

  // 给基础字符串 p 设置个数
  for (let i = 0; i < pLen; i++) {
    // 字符出现字数计数
    needMap.set(p[i], (needMap.get(p[i]) || 0) + 1);
  }
  /**
   * 出现足够次数的字母 则计数
   * 假设：  aab 是 p，a 出现了两次，那么需要在 s 中找到两个 a，才计数一次
   * 因为异位字串不计顺序，所以可以用计数的方式判断是否出现足够次数
   */
  let valid = 0;
  // 窗口滑动首要条件：右侧指针小于字符串长度
  while (right < s.length) {
    // 右侧字符串
    const sr = s[right];
    // 记录出现的次数
    windowMap.set(sr, (windowMap.get(sr) || 0) + 1);
    // 如果出现的次数和子串相同 valid +1
    if (needMap.get(sr) === windowMap.get(sr)) {
      valid++;
    }
    // 左侧窗口收缩：窗口长度等于 p 长度
    while (right - left + 1 === pLen) {
      // 如果计数等于 needMap size 说明 本次找到符合条件的字串
      if (valid === needMap.size) {
        // 开始索引 push 到数组
        indexList.push(left);
      }
      // 左侧字符串
      const sl = s[left];
      //收缩前 如果左侧字符刚好等于出现的字符，valid 需要-1，因为不够数量
      if (needMap.get(sl) === windowMap.get(sl)) {
        valid--;
      }
      // 计数-1
      windowMap.set(sl, windowMap.get(sl) - 1);
      // 收缩左窗口指针，以便下次循环
      left++;
    }
    // 右侧指针扩展
    right++;
  }
  // 返回最终结果
  return indexList;
};