使用win滑动窗口记录字符出现的次数 遍历s,增减窗口,检测窗口是否全为0,是 i - p.length + 1 就是一个答案
var findAnagrams = function (s, p) {
const res = [], win = {}, need = {}, pLen = p.length;
let len = 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[j] in need && win[s[j]]-- === need[s[j]]) len++;
if (s[i] in need && ++win[s[i]] === need[s[i]]) len--;
if (len === 0) res.push(j + 1);
}
return res;
};
- 时间复杂度:O(s)
- 空间复杂度:O(1)