介绍

滑动窗口是一种解决问题的思路和方法，通常用来解决一些连续问题。 比如 LeetCode 的 209. 长度最小的子数组。更多滑动窗口题目见下方题目列表。

常见套路

滑动窗口主要用来处理连续问题。比如题目求解“连续子串 xxxx”，“连续子数组 xxxx”，就应该可以想到滑动窗口。能不能解决另说，但是这种敏感性还是要有的。
从类型上说主要有：

• 固定窗口大小
• 窗口大小不固定，求解最大的满足条件的窗口
• 窗口大小不固定，求解最小的满足条件的窗口（上面的 209 题就属于这种）

后面两种我们统称为可变窗口。当然不管是哪种类型基本的思路都是一样的，不一样的仅仅是代码细节。

固定窗口大小

对于固定窗口，我们只需要固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点，并且保证：

• l 初始化为 0,初始化 r，使得 r - l + 1 等于窗口大小,同时移动 l 和 r
• 判断窗口内的连续元素是否满足题目限定的条件
• 如果满足，再判断是否需要更新最优解，如果需要则更新最优解, 如果不满足，则继续。

可变窗口大小

对于可变窗口，我们同样固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点。后面有所不同，我们需要保证：

• l 和 r 都初始化为 0,r 指针移动一步,判断窗口内的连续元素是否满足题目限定的条件
• 如果满足，再判断是否需要更新最优解，如果需要则更新最优解。并尝试通过移动 l 指针缩小窗口大小。 如果不满足，则继续。

形象地来看的话，就是 r 指针不停向右移动，l 指针仅仅在窗口满足条件之后才会移动，起到窗口收缩的效果。

初始化慢指针 = 0
初始化 ans

for 快指针 in 可迭代集合
   更新窗口内信息
   while 窗口内不符合题意
      扩展或者收缩窗口
      慢指针移动
   更新答案
返回 ans

Leetcode209

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        l = total = 0
        ans = len(nums) + 1
        for r in range(len(nums)):
            total += nums[r]
            while total >= s:
                ans = min(ans, r - l + 1)
                total -= nums[l]
                l += 1
        return  0 if ans == len(nums) + 1 else ans

题目推荐：
Leetcode3. 无重复字符的最长子串

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l=0
        ans=0
        res=0
        for r in range(len(s)):
            if s[r] not in s[l:r]:
                ans+=1
            else:
                while s[l]!=s[r]:
                    l+=1
                l+=1
                ans=r-l+1
            res=max(res,ans)
        return res

Leetcode76. 最小覆盖子串

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need=collections.defaultdict(int)
        for c in t:
            need[c]+=1
        needCnt=len(t)
        i=0
        res=(0,float('inf'))
        for j,c in enumerate(s):
            if need[c]>0:
                needCnt-=1
            need[c]-=1
            if needCnt==0:       #步骤一：滑动窗口包含了所有T元素
                while True:      #步骤二：增加i，排除多余元素
                    c=s[i] 
                    if need[c]==0:
                        break
                    need[c]+=1
                    i+=1
                if j-i<res[1]-res[0]:   #记录结果
                    res=(i,j)
                need[s[i]]+=1  #步骤三：i增加一个位置，寻找新的满足条件滑动窗口
                needCnt+=1
                i+=1
        return '' if res[1]>len(s) else s[res[0]:res[1]+1]    #如果res始终没被更新过，代表无满足条件的结果

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

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        p=sorted(list(p))
        n=len(p)
        l=0
        res=[]
        while l+n<=len(s):
            if sorted(list(s[l:(l+n)]))==p:
                res.append(l)
            l+=1
        return res

Leetcode904. 水果成篮

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        baskets=[]
        l=0
        ans=0
        res=0
        for r in range(len(fruits)):#三种情况分别讨论
            if fruits[r] in baskets:
                ans+=1
            elif len(baskets)<2:
                baskets.append(fruits[r])
                ans+=1
            else:
                for b in baskets:
                    if b!=fruits[r-1]:
                        break
                baskets=[fruits[r],fruits[r-1]]
                l=r
                while fruits[l]!=b and l>0:
                    l-=1
                l+=1
                ans=r-l+1
            res=max(res,ans)
        return res

Leetcode930. 和相同的二元子数组
Leetcode992. K 个不同整数的子数组
Leetcode978. 最长湍流子数组
Leetcode1004. 最大连续 1 的个数 III
Leetcode1234. 替换子串得到平衡字符串
Leetcode1248. 统计「优美子数组」
Leetcode1658. 将 x 减到 0 的最小操作数