438. 找到单词中所有字母异位词.md

思路

使用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)