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

https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

解法一：滑动窗口

由于子串是连续的，因此在滑动窗口模板的基础上，增加条件：当窗口>=t串时，左侧收缩 秒出

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res =[]
        need = {}
        window = {}
        for c in p:
            need[c] = need.get(c, 0)+1
        left = 0  # 窗口左边界
        right = 0  # 窗口右边界
        start = 0  # 记录子串起点

        valid = 0  # p串与s串匹配次数
        while right < len(s):
            # 增大窗口
            c = s[right]
            right += 1
            if c in need:  # 该字符在p串中
                window[c] = window.get(c, 0)+1
                if window[c] == need[c]:  # 该字符匹配
                    valid += 1
            while right-left >= len(p):	 #缩小窗口
                if valid == len(need):	#完全匹配时，将左侧边界填入结果
                    res.append(left)

                d = s[left]
                left += 1
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        return res