滑动窗口问题汇总（有解决模板）

0、粗解滑动窗口定义：

目的：减少while循环
for example: a = [1,4,2,3,4,5,6]取最大的连续三个数。

1. 暴力法：（伪代码）

for i in range(len(a)):
	for j in range(i,i+k-1):
		sum += a[j]
		max_sum = max(sum,max_sum))

• 时间复杂度：$O(n\ast k)$
• 空间复杂度：$O(1)$

2. 滑动窗口
   在暴力法中，第$i$次计算了（1, 4, 2）的和，第$i+1$次计算了（4,2,3）的和，可以看出，这两次计算重复计算了(4,2)的和
   so，滑动窗口就是为了减少两个窗口相交部分的重复计算
   具体：

• 时间复杂度：$O(n$
• 空间复杂度：$O(1)$

1、滑动窗口解决模板

• 手写：
  
• 代码（python）

class Solution:
    def problemName(self, s: str) -> int:
        # Step 1: 定义需要维护的变量们 (对于滑动窗口类题目，这些变量通常是最小长度，最大长度，或者哈希表)
        x, y = ..., ...

        # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
        start = 0
        for end in range(len(s)):
            # Step 3: 更新需要维护的变量, 有的变量需要一个if语句来维护 (比如最大最小长度)
            x = new_x
            if condition:
                y = new_y

            '''
            ------------- 下面是两种情况，读者请根据题意二选1 -------------
            '''
            # Step 4 - 情况1
            # 如果题目的窗口长度固定：用一个if语句判断一下当前窗口长度是否达到了限定长度 
            # 如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变, 
            # 左指针移动之前, 先更新Step 1定义的(部分或所有)维护变量 
            if 窗口长度达到了限定长度:
                # 更新 (部分或所有) 维护变量 
                # 窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变

            # Step 4 - 情况2
            # 如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
            # 如果当前窗口不合法时, 用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
            # 在左指针移动之前更新Step 1定义的(部分或所有)维护变量 
            while 不合法:
                # 更新 (部分或所有) 维护变量 
                # 不断移动窗口左指针直到窗口再次合法

        # Step 5: 返回答案
        return ...

2、例题演示

（1）LC209 长度最小的子数组（中等）

题目

找到正整数数组nums的总和大于等于target的 连续子数组，返回字数组长度，不存在，返回0。

代码（python）

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if nums is None or len(nums) == 0:
            return 0
        # 滑动窗口（不定长问题）
        # Step 1: 定义需要维护的变量们 
        sum = 0
        n = len(nums)
        res = n + 1
        # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口      
        start = 0
        end = 0
        while end < n:
            # Step 3: 更新需要维护的变量
            sum += nums[end]
            # Step 4 - 情况2
            # 如果当前窗口不合法时, 用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
            while sum >= target:
                # 在左指针移动之前更新Step 1定义的(部分或所有)维护变量 
                res = min(res,end-start+1)
                sum -= nums[start]
                start += 1
            end += 1 
        if res == n + 1:
            return 0
        else:
            return res

（2）LC1456 定长字符串的元音最大数目

题目

给你字符串 s 和整数 k 。请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

代码（python）

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        if s is None or len(s)==0 or len(s)<k:
            return 0
        # Step 1: 定义需要维护的变量们 (对于滑动窗口类题目，这些变量通常是最小长度，最大长度，或者哈希表)
        count = 0 # 记录当前元音数量
        max_count = 0 #保存最大的元音数量
        hashset = set(['a','e','i','o','u']) # 创建哈西集，方便判断元素是否为元音O（1）
        # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
        start = 0
        for end in range(len(s)):
            # Step 3: 更新需要维护的变量, 有的变量需要一个if语句来维护 (比如最大最小长度)
            if s[end] in hashset:
                count += 1
            if end - start == k-1:
                max_count = max(max_count,count) 
            # Step 4 - 情况1
            # 如果题目的窗口长度固定：用一个if语句判断一下当前窗口长度是否达到了限定长度 
            if end - start >= k:
                # 左指针移动之前, 先更新Step 1定义的(部分或所有)维护变量 
                if s[start] in hashset:
                    count -= 1
                start +=1
                max_count = max(max_count,count)        
        return max_count

未完待续。。。