滑动窗口.md

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

核心方法：滑动窗口

• 时间复杂度：O(M+N)，M 和 N 分别是字符串 s 和 p 的长度。因为我们先用 for 循环遍历了字符串 p 来初始化 need，时间 O(N)，之后的两个 while 循环最多执行 2M 次，时间 O(M)。
• 空间复杂度：window 和 need 产生的空间，最坏情况下是 O(N)，即 p 的长度

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # 统计字符串p中所有字母出现的次数，初始化窗口
        window = collections.defaultdict(int)
        need = collections.Counter(p)
        left, right = 0, 0
        valid = 0  # 表示窗口内不同字符个数满足p中对应字符个数的数量
        res = list()
        while right < len(s):
            ch = s[right]
            right += 1
            # 窗口内的数据更新，添加新加入的字符
            if need[ch]:
                window[ch] += 1
                if need[ch] == window[ch]:
                    # 如果一个字符在窗口和p中出现次数相同，valid就加1
                    valid += 1
            while (right - left) >= len(p):
                # while内为判断左侧窗口是否需要收缩
                if valid == len(need):
                    # 这里判断是否找到了合法子串
                    res.append(left)
                d = s[left]
                left += 1
                # 窗口内的数据更新，删掉左侧字符
                if need[d]:
                    if need[d] == window[d]:
                        valid -= 1
                    window[d] -= 1
        return res

76，最小覆盖子串，困难

核心方法：滑动窗口

• 时间复杂度：O(M+N)，M 和 N 分别是字符串 S 和 T 的长度。因为我们先用 for 循环遍历了字符串 T 来初始化 need，时间 O(N)，之后的两个 while 循环最多执行 2M 次，时间 O(M)。
• 空间复杂度：window 和 need 产生的空间，最坏情况下是 O(N)，即 T 的长度

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        window = collections.defaultdict(int)
        need = collections.Counter(t)
        left, right = 0, 0
        valid = 0
        # 最小子串起始位置和长度，长度的初始值为len(s)+1，因为这个最小长度最大不会超过len(s)
        start, min_len = 0, len(s) + 1
        while right < len(s):
            ch = s[right]
            right += 1
            # 更新窗口数据
            if need[ch]:
                window[ch] += 1
                if window[ch] == need[ch]:
                    valid += 1
            while valid == len(need):
                # while 内为判断左侧窗口是否需要收缩的条件
                if right - left < min_len:
                    # 更新最小长度
                    start = left
                    min_len = right - left
                d = s[left]
                left += 1
                # 更新窗口数据
                if need[d]:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        return s[start: start+min_len] if min_len != len(s) + 1 else ''

3，无重复字符的最长子串，中等

核心方法：滑动窗口

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window = collections.defaultdict(int)
        left, right = 0, 0
        res = 0
        while right < len(s):
            ch = s[right]
            right += 1
            # 窗口的数据更新
            window[ch] += 1
            while window[ch] > 1:
                # 判断窗口是否要收缩
                # while内的条件表示，窗口内已经出现重复字符了，需要进行左移
                d = s[left]
                left += 1
                # 窗口数据更新
                window[d] -= 1
            # 更新满足条件的最长子串长度
            res = max(res, right - left)
        return res

567，字符串的排列，中等

核心方法：滑动窗口

这个题和找到字母异位词那个题有点像

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        window = collections.defaultdict(int)
        need = collections.Counter(s1)
        left, right = 0, 0
        valid = 0
        while right < len(s2):
            c1 = s2[right]
            right += 1
            if need[c1]:
                window[c1] += 1
                if need[c1] == window[c1]:
                    valid += 1
            while right - left == len(s1):
                # 由于字符串的排列指的是只包含s1中本身的元素，不包含别的元素
                # 所以窗口内每获取到长度为len(s1)的字符串，就检查一次
                if valid == len(need):
                    # 如果当前窗口内满足s1中所有元素及个数，那么直接返回True，说明找到了
                    return True
                c2 = s2[left]
                left += 1
                if need[c2]:
                    if need[c2] == window[c2]:
                        valid -= 1
                    window[c2] -= 1
        # 循环完成，说明没有找到，返回False
        return False