leetcode438.找到字符串中所有字母异位词

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

异位词 指字母相同，但排列不同的字符串。

*思路

1. left,right指针都s开头，用Map保存p字母的个数。
2. 移动right指针，若字母是p中存在的字母则保存进window，当指针移动的个数等于p了，就开始比较

若window的size等于p则 它们一定是异位词。然后继续移动left指针，挨个挨个比较

 let s = "cbaebabacd", p = "abc"
        var findAnagrams = function (s, p) {
            const res = []
            const need = new Map()
            for (let i = 0; i < p.length; i++) {
                need.set(p[i], need.has(p[i]) ? need.get(p[i]) + 1 : 1)
                console.log(need, i);
            }
            let left = 0, right = 0, valid = 0
            const window = new Map()
            while (right < s.length) {
                const c = s[right]
                right++
                if (need.has(c)) {
                    //如果c是p中存在的的字符
                    window.set(c, window.has(c) ? window.get(c) + 1 : 1)
                    // 当窗口中的字符数和滑动窗口中的字符数一致
                    if (window.get(c) === need.get(c)) {
                        // 有效字符自增
                        valid++
                    }
                }
                console.log(right, valid);
                // 当滑动窗口的大小超出p串长度时 收缩窗口
                while (right - left >= p.length) {
                    // 有效字符和所需字符数一致 找到一条符合条件的子串
                    if (valid === need.size) {
                        res.push(left)
                    }
                    const d = s[left]
                    left++
                    console.log(left, right, c, d);
                    // 如果离开窗口字符是所需字符
                    if (need.has(d)) {
                        // 如果离开字符数和所需字符数一致
                        if (window.get(d) === need.get(d)) {
                            // 有效字符减少一个
                            valid--
                        }
                        // 更新滑动窗口中的字符数
                        window.set(d, window.get(d) - 1)
                    }
                }
            }
            return res