滑动窗口算法模板

伪代码：

//1.维护l,r作为当前窗口的左右边界，先扩大右边界，直至满足可行解
//2.再增大l，直至不满足可行解，增大l期间不断更新结果
//3.重复2+3，直至r到达右边界

滑动窗口模板——内外双while:

left = 0
right = 0

while right < len(nums):
    right_ele = s[right]
    # 无差别自增right
    right += 1
    
    # 无脑将right_ele纳入窗口。这表示需要更新当前窗口的各种必要状态
    window.add(right_ele)
    
    # 如果在前面增大窗口后，发现可以缩小窗口
    if window needs shrink:
        while left <= right or any other condition:
            left_ele = s[left]
            # 无差别自增left
            left += 1
            # 无脑将left_ele踢出窗口。这表示需要更新当前窗口的各种必要状态（增大窗口时更新了啥现在也得更新啥）
            window.remove(left_ele)
            # 如果发现窗口缩小后不满足窗口限制条件了，break
            if window does not need shrink:
                break

可以看到，自增right和自增left的代码神乎其似

滑动窗口算法适用问题

滑动窗口是一个连续的窗口，因此它适合解决连续子串问题。同时，滑动窗口增大或者缩小的判断条件是【检测右边界或者左边界上的元素】，也就是通过检查单个元素（如单个数字、单个字符等）是否符合条件，来缩放窗口。因此，滑动窗口是用来判断，特定字符是否应该出现在窗口中，并且达到相应的出现次数

综上，滑动窗口算法适用于解决【窗口内需要出现特定的字符和相应次数的问题】

例

1.请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 不含重复字符，表示是基于字符的统计；子字符串，连续子串问题 -> 滑动窗口

        char_counter = dict()
        l = len(s)
        res = 0

        # 窗口左右边界
        left = 0
        right = 0
        # 双while模板
        while right < l:
            c = s[right]
            right += 1

            # 无脑将c纳入窗口
            if c not in char_counter:
                char_counter[c] = 1
                res = max(res, right-left)
            else:
                char_counter[c] += 1
                       
            # 如果满足缩小窗口的条件
            if char_counter[c] > 1:                
                while left < right:
                    cc = s[left]
                    left += 1
                    # 无脑将cc从窗口踢出
                    char_counter[cc] -= 1
                    if char_counter[cc] == 0:
                        del char_counter[cc]
                    # 重复元素计数为1时，break
                    if char_counter[c] == 1:
                        break
        return res

2.leetcode#### 76. 最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串
从一个字符串判断另一个字符串的问题的一般思路，通常也是滑动窗口法。因为需要统计窗口内包含的字符及相应的个数

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 保存t中唯一字符计数的字典word_count
        word_count = {}
        for w in t:
            if w in word_count:
                word_count[w] += 1
            else:
                word_count[w] = 1
        size = len(word_count)
        
        # 滑动窗口左右边界
        left, right = 0, 0
        res = ''
        # 保存当前窗口中唯一字符计数的字典
        cur_word_count = {}
        # cur_size 用于跟踪当前窗口中以其所需频率存在多少个唯一字符。
        # 例如 如果t是“AABC”那么窗口必须有两个A，一个B和一个C.
        # 因此，当满足所有这些条件时，cur_size = 3。
        cur_size = 0
        
        ## 下面是滑动窗口核心代码
        while right < len(s):
            right_ele = s[right]
            # 无差别自增right
            right += 1
            # 无脑将right_ele纳入窗口，只有当right_ele在word_count中，才会改变窗口的状态
            if right_ele in word_count:
                if right_ele in cur_word_count:
                    cur_word_count[right_ele] += 1
                else:
                    cur_word_count[right_ele] = 1
                
                if cur_word_count[right_ele] == word_count[right_ele]:
                    cur_size += 1

            # 如要缩小窗口
            if cur_size == size:
                while left < right:
                    left_ele = s[left]
                    left += 1
                    # # 无脑将left_ele踢出窗口，只有当left_ele在word_count中，才会改变窗口的状态
                    if left_ele in word_count:
                        if left_ele in cur_word_count:
                            cur_word_count[left_ele] -= 1
                            if cur_word_count[left_ele] < word_count[left_ele]:
                                cur_size -= 1
                                break
                            
                if not res:
                    res = s[left-1:right]
                else:
                    res = s[left-1:right] if (right-left+1) < len(res) else res 
        return res

3.leetcode#### 567. 字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。
这一题和上一题类似的

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        l_s1 = len(s1)
        l = len(s2)
        left = right = 0

        word_count = {}
        for ele in s1:
            if ele not in word_count:
                word_count[ele] = 1
            else:
                word_count[ele] += 1
        # s1包含的字符种数
        word_kinds = len(word_count)

        cur_word_count = {}
        cur_word_kinds = 0
        # 滑动窗口
        while right < l:
            ele = s2[right]
            # 无差别自增right
            right += 1
            # 维护ele加入窗口后的各种必要状态
            if ele in word_count:
                if ele not in cur_word_count:
                    cur_word_count[ele] = 1
                else:
                    cur_word_count[ele] += 1
                # ele在s2中出现次数与在s1中出现次数一致时，窗口字符种数+1
                if cur_word_count[ele] == word_count[ele]:
                    cur_word_kinds += 1
            
            if cur_word_kinds == word_kinds:
                while left != right - l_s1:
                    c = s2[left]
                    left += 1
                    # 维护c脱离窗口后的各种必要状态
                    if c in cur_word_count:
                        cur_word_count[c] -= 1
                        if cur_word_count[c] < word_count[c]:
                            cur_word_kinds -= 1
                            break    
                else:
                    return True
        return False