前言

滑窗算法常用于序列的连续子序列的处理。通过两个指针维护一个窗口，通过一些逻辑对这个窗口——亦即一个连续的子序列——进行处理。

简单的例子：最长无公共字母的子串

这道题可以通过LeetCode 3访问，一个AC解是：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        d = {}
        res = 0
        l, r = 0, 0
        while r < len(s):
            while l < r and s[r] in d:
                d.pop(s[l])
                l += 1
            d[s[r]] = 1
            res = max(r-l+1, res)
            r += 1
        return res

这道题通过左右指针+哈希表的结构维护一个区间，哈希表记录这个区间内的字母的出现次数。右指针不断移动，迭代每一个字母，如果右指针的移动带来了字母的重复，就移动左指针，直到没有重复字母为止。

滑窗算法的步骤通常是：

1. 编写维护连续区间的逻辑：这要求预先判断出，题目涉及到连续子序列的操作，可以通过滑窗求解。具体考虑时，需要考虑该怎么维护，单纯的滑窗？滑窗加上一些外部数据结构？
2. 迭代过程的处理：思考边界条件是什么？两个指针在什么条件下移动？

简单的例子：模式串的排列匹配

这道题可以通过LeetCode 567访问，一个AC解是：

class Solution:
    def isSameDict(self, d1, d2):
        if len(d1) != len(d2):
            return False
        for k1 in d1.keys():
            if k1 not in d2:
                return False
            if d2[k1] != d1[k1]:
                return False
        return True
    
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        d1, d2 = {}, {}
        for c1 in s1:
            if c1 in d1:
                d1[c1] += 1
            else:
                d1[c1] = 1
        l, r = 0, len(s1) - 1
        for idx in range(r+1):
            c2 = s2[idx]
            if c2 in d2:
                d2[c2] += 1
            else:
                d2[c2] = 1
        while r < len(s2):
            if self.isSameDict(d1, d2):
                return True
            if d2[s2[l]] == 1:
                d2.pop(s2[l])
            else:
                d2[s2[l]] -= 1
            l += 1
            r += 1
            if r == len(s2):
                break
            if s2[r] in d2:
                d2[s2[r]] += 1
            else:
                d2[s2[r]] = 1
        return False

这道题通过滑窗+哈希表的结构维护区间内部的信息。通过题干，很容易发现是连续序列的处理，那么字母的排列不会影响长度，就代表滑窗的窗口大小固定了。依次迭代，发现字母出现的次数与模式串一致，就代表匹配成功了。

简单的例子：替换后可出现的最长单字母串

这道题可通过LeetCode 424访问，一个AC解是：

class Solution:
    def getMinDiffCharTime(self, d):
        if len(d) <= 1:
            return 0
        maxi = 0
        total = 0
        for v in d.values():
            maxi = max(maxi, v)
            total += v
        return total - maxi
    def characterReplacement(self, s: str, k: int) -> int:
        d = {}
        l = 0
        result = 0
        for r in range(len(s)):
            d[s[r]] = d[s[r]] + 1 if s[r] in d else 1
            while l < r and self.getMinDiffCharTime(d) > k:
                if d[s[l]] == 1:
                    d.pop(s[l])
                else:
                    d[s[l]] -= 1
                l += 1
            result = max(result, r-l+1)
        return result

这道题的答案我并没有优化，完全可以通过定长list优化哈希表。不过，这道题依然是通过哈希表+滑窗进行序列的维护。