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

给定两个字符串 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 * 10^4
• s 和 p 仅包含小写字母

滑动窗口+哈希表

need Map是不变的，window map是可变的，valid变量也是可变的。移动窗口左右边界后都要更新window和valid。右边界右移是无条件的，左边界右移的条件是窗口中的元素个数等于输入的字符串的元素的个数。左移前还要检查valid是否达到要求，如果达到，则记录结果。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // 初始化变量
        int left = 0; // 窗口左边界
        int right = 0; // 窗口右边界
        int valid = 0; // 窗口中合格的字符个数
        List<Integer> res = new LinkedList<>(); // 结果列表，存储字母异位词子串的起始索引
        Map<Character, Integer> window = new HashMap<>(); // 当前窗口中的字符频率。注意不需要是当前窗口中的所有字符，只需要是当前窗口中的属于p的字符。
        Map<Character, Integer> need = new HashMap<>(); // p 字符串中字符的频率

        // 初始化 need 字典
        for (char c : p.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        // 移动右边界扩展窗口
        while (right < s.length()) {
            char c = s.charAt(right); // 获取右边界字符
            right++; // 右边界右移
            if (need.containsKey(c)) { // 如果右边界字符是 p 中需要的字符
                window.put(c, window.getOrDefault(c, 0) + 1); // 更新窗口中该字符的频率
                if (need.get(c).equals(window.get(c))) { // 如果窗口中该字符的频率达到需要的频率
                    valid++; // 符合条件的字符个数加一
                }
            }

            // 判断窗口大小是否符合要求，调整左边界。right-left是窗口中元素的个数，
            // 例如，一开始right=1，left=0。为什么不是right-left+1？因为把right对应的字符加入窗口后right就自增了。
            // 注意窗口长度等于p的长度时也要缩小窗口，因为满足条件的字符串只可能在窗口长度大于等于p的长度时出现，
            // 在窗口长度小于p的长度时不可能出现。这里改成==也可以。
            while (right - left >= p.length()) {
                if (valid == need.size()) { // 如果窗口中所有需要的字符频率都达到要求
                    res.add(left); // 将左边界加入结果列表
                }
                
                char d = s.charAt(left); // 获取左边界字符
                if (need.containsKey(d)) { // 如果左边界字符是 p 中需要的字符
                    if (need.get(d).equals(window.get(d))) { // 如果窗口中该字符的频率达到需要的频率
                        valid--; // 符合条件的字符个数减一
                    }
                    window.put(d, window.get(d) - 1); // 更新窗口中该字符的频率
                }
                left++; // 左边界右移
            }
        }

        return res; // 返回结果列表
    }
}

• 时间复杂度：O(m+(n−m)×Σ)，其中 n 为字符串 s 的长度，m 为字符串 p 的长度，Σ 为所有可能的字符数。 我们需要 O(m) 来统计字符串 p 中每种字母的数量；需要 O(m) 来初始化滑动窗口；需要判断 n−m+1 个滑动窗口中每种字母的数量是否与字符串 p 中每种字母的数量相同， 每次判断需要 O(Σ)。因为 s 和 p 仅包含小写字母，所以 Σ=26。

• 空间复杂度：O(Σ)。用于存储字符串 p 和滑动窗口中每种字母的数量。