438. [✔][M]找到字符串中所有字母异位词

给定两个字符串 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 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

---

题解：

滑动窗口问题

/*
 * @lc app=leetcode.cn id=438 lang=typescript
 *
 * [438] 找到字符串中所有字母异位词
 */

// @lc code=start
function findAnagrams(s: string, p: string): number[] {
    let win = new Map(),need = new Map();
    for (const c of p) {
        need.set(c, (need.get(c) || 0) + 1);
    }

    let left = 0;
    let right = 0;

    let vaild = 0;

    let res: number[] = [];

    while (right < s.length) {
        let c = s[right];
        right++;

        if (need.get(c)) {
            win.set(c, (win.get(c) || 0) + 1);
            if (win.get(c) === need.get(c)) {
                vaild++;
            }
        }

        while (right - left >= p.length) {
            if (vaild === need.size) {
                res.push(left)
            }
            let d = s[left];
            left++;
            if (need.get(d)) {
                if (need.get(d) === win.get(d)) {
                    vaild--;
                }
                win.set(d, win.get(d) - 1);
            }
        }
    }

    return res;
};
// @lc code=end