滑动窗口是一种很高效的寻找特定情况字串的一种算法。一个题求某种符合条件的字串，穷举的话就只能是固定起点和终点。然后获取到所有的字串，判断是否符合条件，时间复杂度是$O(n^2)$.而滑动窗口看似是两个嵌套的循环，但是对于字符串的每个字符来说，都只被遍历了一遍，所以时间复杂度是$O(n)$

滑动窗口的模板代码如下：

# 滑动窗口算法伪码框架
def slidingWindow(s: str):
    # 用合适的数据结构记录窗口中的数据，根据具体场景变通
    # 比如说，我想记录窗口中元素出现的次数，就用 map
    # 如果我想记录窗口中的元素和，就可以只用一个 int
    window = ...

    left, right = 0, 0
    while right < len(s):
        # c 是将移入窗口的字符
        c = s[right]
        window.add(c)
        # 增大窗口
        right += 1
        # 进行窗口内数据的一系列更新
        ...

        # *** debug 输出的位置 ***
        # 注意在最终的解法代码中不要 print
        # 因为 IO 操作很耗时，可能导致超时
        # print(f"window: [{left}, {right})")
        # ***********************

        # 判断左侧窗口是否要收缩
        while left < right and window needs shrink:
            # d 是将移出窗口的字符
            d = s[left]
            window.remove(d)
            # 缩小窗口
            left += 1
            # 进行窗口内数据的一系列更新
            ...

对于滑动窗口问题，我们需要考虑以下三个问题：

1、什么时候应该移动 right 扩大窗口？窗口加入字符时，应该更新哪些数据？

2、什么时候窗口应该暂停扩大，开始移动 left 缩小窗口？从窗口移出字符时，应该更新哪些数据？

3、什么时候应该更新结果？

只要能回答这三个问题，就说明可以使用滑动窗口技巧解题。

76. 最小覆盖子串

这个题会了，下面的几个题基本就没什么难度了。我们需要用到几个变量，need存储目标窗口，window存储当前窗口，vaild存储当前窗口满足目标窗口元素的个数。left和right就是快慢指针。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        window = dict()
        need = dict()
# 把目标串存到目标窗口
        for i in t:
            need[i] = need.get(i, 0) + 1
        vaild = 0
        left = right = 0
        length = float("inf")
        res = ""
        while right < len(s):
            c = s[right]
            right += 1
# 如果字符在need窗口里面就让计数器+1
            if c in need:
                window[c] = window.get(c, 0) + 1
# 如果这个字符满足条件了，就让vaild+1
                if window[c] == need[c]:
                    vaild += 1
# 当vaild和目标窗口长度相同，就代表所有元素都满足条件了，尝试缩小窗口
            while vaild == len(need):
# 此时的子串就是一个符合条件的子串，尝试更新答案
                if length > right - left:
                    res = s[left:right]
                    length = right - left
                c = s[left]
                left += 1
# 缩小窗口，更新相关的数据。
                if c in need:
                    if window[c] == need[c]:
                        vaild -= 1
                    window[c] -= 1
        return res

567. 字符串的排列

这个题目也是类似的,内层循环我写成了if，因为题目要求的是s1的一种排列，一旦长度超过s1的长度那肯定是不符合条件的，所以这个题其实是在维护一个定长的窗口不停的向右滑动。窗口长度和s1相同的时候就判断一下是否满足条件，不满足条件就向右缩小一格，然后在下一次又添加一格，又符合长度了。使用if就可以了。

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        need = dict()
        window = dict()
        for i in s1:
            need[i] = need.get(i, 0) + 1
        vaild = left = right = 0
        while right < len(s2):
            c = s2[right]
            right += 1
            if c in need:
                window[c] = window.get(c, 0) + 1
                if window[c] == need[c]:
                    vaild += 1
            if right - left >= len(s1):
                if vaild == len(need):
                    return True
                c = s2[left]
                left += 1
                if c in need:
                    if window[c] == need[c]:
                        vaild -= 1
                    window[c] -= 1
        return False

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

这个题和567题是一样的，同样的定长字符串，只不过求的不是是否存在，而是找到了要把这个子串的起始索引存起来就行了。

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        need = dict()
        windows = dict()
        vaild = left = right = 0
        res = []
        for i in p:
            need[i] = need.get(i, 0) + 1
        while right < len(s):
            c = s[right]
            right += 1
            if c in need:
                windows[c] = windows.get(c, 0) + 1
                if windows[c] == need[c]:
                    vaild += 1
            if right - left >= len(p):
                if vaild == len(need):
                    res.append(left)
                c = s[left]
                left += 1
                if c in need:
                    if windows[c] == need[c]:
                        vaild -= 1
                    windows[c] -= 1
        return res

3. 无重复字符的最长子串

这个题稍微有点新意，但是更简单了。连need窗口也不需要了，当窗口没有重复的元素的时候，开始扩大窗口，当窗口出现重复的元素的时候，就尝试让它不重复。在内层while结束之后，就是一个符合条件的子串，然后更新答案即可。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = right = 0
        window = dict()
        length = 0
        while right < len(s):
            c = s[right]
            right += 1
            window[c] = window.get(c, 0) + 1
            while window[c] >= 2:
                new_c = s[left]
                left += 1
                window[new_c] -= 1
            if right - left > length:
                length = right - left
        return length