思路

使用win滑动窗口记录字符出现的次数遍历s，增减窗口，检测窗口是否全为0，是 i - p.length + 1 就是一个答案

代码

  1. var findAnagrams = function (s, p) {
  2.     const res = [], win = {}, need = {}, pLen = p.length;
  3.     let len = 0;
  4.     for (const x of p) {
  5.         if (need[x] === undefined) {
  6.             need[x] = win[x] = 0;
  7.             len++;
  8.         }
  9.         need[x]++;
  10.     }
  11.     for (let i = 0; i < s.length; i++) {
  12.         const j = i - pLen;
  13.         if (s[j] in need && win[s[j]]-- === need[s[j]]) len++;
  14.         if (s[i] in need && ++win[s[i]] === need[s[i]]) len--;
  15.         if (len === 0) res.push(j + 1);
  16.     }
  17.     return res;
  18. };

复杂度分析

  • 时间复杂度：O(s)
  • 空间复杂度：O(1)