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

该题解采用了滑动窗口的方法。首先，使用一个哈希表 need 记录字符串 p 中每个字符的出现次数。然后，使用另一个哈希表 window 来记录当前窗口中各字符的出现次数。接着，不断扩展右边界 right，直到窗口中包含了 p 中所有字符。此时，开始收缩左边界 left，直到窗口中不再包含 p 的所有字符。在收缩的过程中，如果窗口的长度恰好等于 p 的长度，则说明找到了一个异位词的起始索引，将其添加到结果列表中。重复这个过程，直到遍历完字符串 s。

时间复杂度: O(n)

空间复杂度: O(p)

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        need = {}
        for c in p:  # 统计 p 中每个字符出现的次数
            need[c] = need.get(c, 0) + 1
        window = {}
        left, right = 0, 0  # 定义滑动窗口的左右边界
        valid = 0  # 用于记录窗口中满足 need 条件的字符个数
        res = []  # 存储结果
        while right < len(s):
            c = s[right]  # 将即将移入窗口的字符
            right += 1  # 右移窗口
            if c in need:
                window[c] = window.get(c, 0) + 1  # 更新窗口中的字符计数
                if window[c] == need[c]:  # 如果字符 c 的数量满足了 need 中的要求
                    valid += 1
            while valid == len(need):  # 当窗口满足所有字符需求时
                if right - left == len(p):  # 如果窗口大小等于 p 的长度
                    res.append(left)  # 添加起始索引到结果列表
                d = s[left]  # 将要移出窗口的字符
                left += 1  # 左移窗口
                if d in need:
                    if window[d] == need[d]:  # 如果字符 d 的数量满足了 need 中的要求
                        valid -= 1  # 减少满足条件的字符个数
                    window[d] -= 1  # 更新窗口中的字符计数
        return res