[滑动窗口真滴简单!] 闪电五连鞭带你秒杀12道中档题 (附详情解析) 原文
最后更新时间: 2021/09/19

不像动态规划，绝大部分滑动窗口类题目本质上真的不算是难题，经过有效的训练就可以熟练掌握。本文中Eason给大家分享一套滑动窗口的思维框架 (共五步-五连鞭)，非常好记和容易理解。掌握它之后，你可以一口气秒杀12道中等难度 的同类型题目 (卧槽？12道？是的，而且给全解析，再不点赞还是人？)，从而帮助你再遇见滑动窗口类型题目的时候不再胆怯！

PS：在这里我就不教大家什么是滑动窗口啦，这个概念并不难，leetcode上类似的科普文也有很多，所以我就不班门弄斧了。如果读者完全没有听说过这个概念，烦请先花10分钟弄懂个大概后再来阅读本文

框架 (伪代码)

  1. class Solution:
  2. def problemName(self, s: str) -> int:
  3. # Step 1: 定义需要维护的变量们 (对于滑动窗口类题目，这些变量通常是最小长度，最大长度，或者哈希表)
  4. x, y = ..., ...
  6.    # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
  7.     start = 0
  8.     for end in range(len(s)):
  9.         # Step 3: 更新需要维护的变量, 有的变量需要一个if语句来维护 (比如最大最小长度)
  10.         x = new_x
  11.         if condition:
  12.             y = new_y
  13.         '''
  14.         ------------- 下面是两种情况，读者请根据题意二选1 -------------
  15.         '''
  16.         # Step 4 - 情况1
  17.         # 如果题目的窗口长度固定：用一个if语句判断一下当前窗口长度是否达到了限定长度 
  18.         # 如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变, 
  19.         # 左指针移动之前, 先更新Step 1定义的(部分或所有)维护变量 
  20.         if 窗口长度达到了限定长度:
  21.             # 更新 (部分或所有) 维护变量 
  22.             # 窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变
  24.         # Step 4 - 情况2
  25.         # 如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
  26.         # 如果当前窗口不合法时, 用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
  27.         # 在左指针移动之前更新Step 1定义的(部分或所有)维护变量 
  28.         while 不合法:
  29.             # 更新 (部分或所有) 维护变量 
  30.             # 不断移动窗口左指针直到窗口再次合法
  32.     # Step 5: 返回答案
  33.     return ...

看不懂？ mode问题，在我们做3. 无重复字符的最长子串这道题前先用这个模板先套一道简单题643. 子数组最大平均数 I (不计算到中等题目中，基本的良心还是得有)
如果套完还不懂，不要担心，让我们再套一道，套完仍然不懂，let’s 再套一道……
我们有共13 (12中1简) 道题，请相信自己，套着套着，咱们终究会弄懂的！

643 子数组最大平均数 I

  1. class Solution:
  2. def findMaxAverage(self, nums: List[int], k: int) -> float:
  3. # Step 1
  4. # 定义需要维护的变量
  5. # 本题求最大平均值 (其实就是求最大和)，所以需要定义sum_, 同时定义一个max_avg (初始值为负无穷)
  6. sum_, max_avg = 0, -math.inf
  7.     # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
  8.     start = 0
  9.     for end in range(len(nums)):
  10.         # Step 3: 更新需要维护的变量 (sum_, max_avg), 不断把当前值积累到sum_上
  11.         sum_ += nums[end]
  12.         if end - start + 1 == k:
  13.             max_avg = max(max_avg, sum_ / k)
  15.         # Step 4
  16.         # 根据题意可知窗口长度固定，所以用if
  17.         # 窗口首指针前移一个单位保证窗口长度固定, 同时提前更新需要维护的变量 (sum_)
  18.         if end >= k - 1:
  19.             sum_ -= nums[start]
  20.             start += 1
  21.     # Step 5: 返回答案
  22.     return max_avg

现在再来让我们看看3. 无重复字符的最长子串这道题，你会发现其实写法也是差不多的，就是多了个哈希表然后if变成了while

3 无重复字符的最长子串

  1. class Solution:
  2. def lengthOfLongestSubstring(self, s: str) -> int:
  3. # Step 1: 定义需要维护的变量, 本题求最大长度，所以需要定义max_len, 该题又涉及去重，因此还需要一个哈希表
  4. max_len, hashmap = 0, {}
  5.     # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
  6.     start = 0
  7.     for end in range(len(s)):
  8.         # Step 3
  9.         # 更新需要维护的变量 (max_len, hashmap)
  10.         # i.e. 把窗口末端元素加入哈希表，使其频率加1，并且更新最大长度
  11.         hashmap[s[end]] = hashmap.get(s[end], 0) + 1
  12.         if len(hashmap) == end - start + 1:
  13.             max_len = max(max_len, end - start + 1)
  15.         # Step 4: 
  16.         # 根据题意,  题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
  17.         # 这时要用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
  18.         # 当窗口长度大于哈希表长度时候 (说明存在重复元素)，窗口不合法
  19.         # 所以需要不断移动窗口左指针直到窗口再次合法, 同时提前更新需要维护的变量 (hashmap)
  20.         while end - start + 1 > len(hashmap):
  21.             head = s[start]
  22.             hashmap[head] -= 1
  23.             if hashmap[head] == 0:
  24.                 del hashmap[head]
  25.             start += 1
  26.     # Step 5: 返回答案 (最大长度)
  27.     return max_len

没懂？没事，让我们再来做个类似的 159. 至多包含两个不同字符的最长子串，这道题和3. 无重复字符的最长子串几乎一模一样

159 至多包含两个不同字符的最长子串

  1. class Solution:
  2. def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
  3. # Step 1:
  4. # 定义需要维护的变量, 本题求最大长度，所以需要定义max_len,
  5. # 该题又涉及计算不重复元素个数，因此还需要一个哈希表
  6. max_len, hashmap = 0, {}
  7.     # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
  8.     start = 0
  9.     for end in range(len(s)):
  10.         # Step 3
  11.         # 更新需要维护的变量 (max_len, hashmap)
  12.         # 首先，把当前元素的计数加一
  13.         # 一旦哈希表长度小于等于2(之多包含2个不同元素)，尝试更新最大长度
  14.         tail = s[end]
  15.         hashmap[tail] = hashmap.get(tail, 0) + 1
  16.         if len(hashmap) <= 2:
  17.             max_len = max(max_len, end - start + 1)
  19.         # Step 4: 
  20.         # 根据题意,  题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
  21.         # 这时要用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
  22.         # 哈希表长度大于2的时候 (说明存在至少3个重复元素)，窗口不合法
  23.         # 所以需要不断移动窗口左指针直到窗口再次合法, 同时提前更新需要维护的变量 (hashmap)
  24.         while len(hashmap) > 2:
  25.             head = s[start]
  26.             hashmap[head] -= 1
  27.             if hashmap[head] == 0:
  28.                 del hashmap[head]
  29.             start += 1
  30.     # Step 5: 返回答案 (最大长度)
  31.     return max_len

还是没有什么感觉? 没问题，再来一道

209 长度最小的子数组

  1. class Solution:
  2. def minSubArrayLen(self, target: int, nums: List[int]) -> int:
  3. # Step 1: 定义需要维护的变量, 本题求最小长度，所以需要定义min_len, 本题又涉及求和，因此还需要一个sum变量
  4. min_len, sum_ = math.inf, 0
  5.       # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
  6.     start = 0
  7.     for end in range(len(nums)):
  8.         # Step 3: 更新需要维护的变量 (min_len, sum_)
  9.         sum_ += nums[end]
  11.         # 这一段可以删除，因为下面的while已经handle了这一块儿逻辑，不过写在这也没影响
  12.         if sum_ >= target:
  13.             min_len = min(min_len, end - start + 1)
  15.         # Step 4
  16.         # 这一题这里稍微有一点特别: sum_ >= target其实是合法的，但由于我们要求的是最小长度，
  17.         # 所以当sum_已经大于target的时候继续移动右指针没有意义，因此还是需要移动左指针慢慢逼近答案
  18.         # 由于左指针的移动可能影响min_len和sum_的值，因此需要在移动前将它们更新
  19.         while sum_ >= target:
  20.             min_len = min(min_len, end - start + 1)
  21.             sum_ -= nums[start]
  22.             start += 1
  23.     # Step 5：返回答案 (最小长度)
  24.     if min_len == math.inf:
  25.         return 0
  26.     return min_len

没有看懂? 没问题，没问题, 再来一道

1695 删除子数组的最大得分

  1. class Solution:
  2. def maximumUniqueSubarray(self, nums: List[int]) -> int:
  3. # Step 1
  4. # 定义需要维护的变量, 本题最大得分，所以需要定义当前得分sum_和最大得分max_sum
  5. # 本题又涉及去重 (题目规定子数组不能有重复)，因此还需要一个哈希表
  6. sum_, max_sum, hashmap = 0, 0, {}
  7.     # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
  8.     start = 0
  9.     for end in range(len(nums)):
  10.         # Step 3
  11.         # 更新需要维护的变量 (sum_, hashmap)
  12.         # sum和hashmap需要更新就不说了，max_sum当且仅当哈希表里面没有重复元素时 (end - start + 1 == len(hashmap)) 更新
  13.         tail = nums[end]
  14.         sum_ += tail
  15.         hashmap[tail] = hashmap.get(tail, 0) + 1
  16.         if end - start + 1 == len(hashmap):
  17.             max_sum = max(max_sum, sum_)
  19.         # Step 4
  20.         # 根据题意,  题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
  21.         # 这时要用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
  22.         # 哈希表里面有重复元素时 (end - start + 1 > len(hashmap)) 窗口不合法
  23.         # 所以需要不断移动窗口左指针直到窗口再次合法, 同时提前更新需要维护的变量 (hashmap， sum_)
  24.         while end - start + 1 > len(hashmap):
  25.             head = nums[start]
  26.             hashmap[head] -= 1
  27.             if hashmap[head] == 0:
  28.                 del hashmap[head]
  29.             sum_ -= nums[start]
  30.             start += 1
  31.     # Step 5: 返回答案
  32.     return max_sum

依旧没完全懂? 没问题，没问题, 没问题, 再来一道!

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

  1. class Solution:
  2. def findAnagrams(self, s: str, p: str) -> List[int]:
  3. # Step 1:
  4. # 定义需要维护的变量
  5. # 本文需要对比两组字符串是否为异位词，所以用哈希表 (abc和bac是异位词是因为他们对应的哈希表相等)
  6. # 同时我们需要找到所有合法解，所以还需要一个res数组
  7. res, hashmap = [], {}
  8.       # Step 1.1： 同时把p的哈希表也建立了 (这个哈希表不需要维护，为定值)
  9.     hashmap_p = {}
  10.     for char in p:
  11.         hashmap_p[char] = hashmap_p.get(char, 0) + 1
  13.     # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
  14.     start = 0
  15.     for end in range(len(s)):
  16.         # Step 3: 更新需要维护的变量 (hashmap)， 如果hashmap == hashmap_p，代表找到了一个解，加入到res
  17.         hashmap[s[end]] = hashmap.get(s[end], 0) + 1
  18.         if hashmap == hashmap_p:
  19.             res.append(start)
  21.         # Step 4 
  22.         # 根据题意可知窗口长度固定，所以用if
  23.         # 窗口左指针前移一个单位保证窗口长度固定, 同时提前更新需要维护的变量 (hashmap)
  24.         if end >= len(p) - 1:
  25.             hashmap[s[start]] -= 1
  26.             if hashmap[s[start]] == 0:
  27.                 del hashmap[s[start]]
  28.             start += 1
  29.     # Step 5: 返回答案
  30.     return res

再来一题！

567 字符串的排列

  1. class Solution:
  2. def checkInclusion(self, s1: str, s2: str) -> bool:
  3. # Step 1
  4. # 定义需要维护的变量
  5. # 因为和排列相关 (元素相同，顺序可以不同)，使用哈希表
  6. hashmap2 = {}
  7.       # Step 1.1: 同时建立s1的哈希表 (这个哈希表不需要维护，为定值)
  8.     hashmap1 = {}
  9.     for char in s1:
  10.         hashmap1[char] = hashmap1.get(char, 0) + 1
  12.     # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
  13.     start = 0
  14.     for end in range(len(s2)):
  15.         # Step 3: 更新需要维护的变量 (hashmap2)， 如果hashmap1 == hashmap2，代表s2包含s1的排列，直接return
  16.         tail = s2[end]
  17.         hashmap2[tail] = hashmap2.get(tail, 0) + 1
  18.         if hashmap1 == hashmap2:
  19.                 return True
  21.         # Step 4: 
  22.         # 根据题意可知窗口长度固定，所以用if
  23.         # 窗口左指针前移一个单位保证窗口长度固定, 同时提前更新需要维护的变量 (hashmap2)
  24.         if end >= len(s1) - 1:
  25.             head = s2[start]
  26.             hashmap2[head] -= 1
  27.             if hashmap2[head] == 0:
  28.                 del hashmap2[head]
  29.             start += 1
  30.     # Step 5： 没有在s2中找到s1的排列，返回False
  31.     return False

再再来一题 (声音开始颤抖)！

487 最大连续1的个数 II

  1. class Solution:
  2. def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
  3. # Step 1
  4. # 定义需要维护的变量
  5. # 因为是求最大长度，所以有max_len，又同时涉及计数 (0的个数不能超过1个)，所以还要一个哈希表
  6. max_len, hashmap = 0, {}
  7.       # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
  8.     start = 0
  9.     for end in range(len(nums)):
  10.         # Step 3: 更新需要维护的变量 (hashmap， max_len)
  11.         tail = nums[end]
  12.         hashmap[tail] = hashmap.get(tail, 0) + 1
  13.         if hashmap.get(0, 0) <= 1:
  14.             max_len = max(max_len, end - start + 1)
  16.         # Step 4
  17.         # 根据题意,  题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
  18.         # 这时要用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
  19.         # 当hashmap里面0的个数大于1的时候，窗口不合法
  20.         # 所以需要不断移动窗口左指针直到窗口再次合法, 同时提前更新需要维护的变量 (hashmap)
  21.         while hashmap.get(0, 0) > 1:
  22.             head = nums[start]
  23.             hashmap[head] -= 1
  24.             start += 1
  25.     # Step 5: 返回答案 (最大长度)
  26.     return max_len

再再再来一题 (声音变得沙哑)！下面一题是上面一题的变种，运用该模板，只需要改一个参数

1004 最大连续1的个数 III

  1. class Solution:
  2. def longestOnes(self, nums: List[int], k: int) -> int:
  3. max_len, hashmap = 0, {}
  4.       start =  0
  5.     for end in range(len(nums)):
  6.         tail = nums[end]
  7.         hashmap[tail] = hashmap.get(tail, 0) + 1
  8.         if hashmap.get(0, 0) <= k:
  9.             max_len = max(max_len, end - start + 1)
  11.         # 相比较于上一题，只需要把1改成k
  12.         while hashmap.get(0, 0) > k:
  13.             head = nums[start]
  14.             hashmap[head] -= 1
  15.             start += 1
  16.     return max_len

[再 for i in range(4)]来一题！ (已经接近失声)

1208 尽可能使字符串相等

  1. class Solution:
  2. def equalSubstring(self, s: str, t: str, max_cost: int) -> int:
  3. # Step 1: 定义需要维护的变量
  4. # 因为是求最大长度，所以有max_len，又同时涉及计算开销 (和求和一个道理)， 所以还要一个cur_cost
  5. cur_cost, max_len = 0, 0
  6.       # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
  7.     start = 0
  8.     for end in range(len(t)):
  9.         # Step 3
  10.         # 更新需要维护的变量 (cur_cost)
  11.         # 每一对字符的order差值就是当前时间点的开销，直接累积在cur_cost上即可
  12.         # cur_cost只要不超过最大开销，就更新max_len
  13.         cur_cost += abs(ord(s[end]) - ord(t[end]))
  14.         if cur_cost <= max_cost:
  15.             max_len = max(max_len, end - start + 1)
  17.         # Step 4
  18.         # 根据题意,  题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
  19.         # 这时要用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
  20.         # 当cur_cost大于最大开销时候，窗口不合法
  21.         # 所以需要不断移动窗口左指针直到窗口再次合法 (cur_cost <= max_cost)
  22.         while cur_cost > max_cost:
  23.             cur_cost -= abs(ord(s[start])-  ord(t[start]))
  24.             start += 1
  25.     # Step 5: 返回答案 (最大长度)
  26.     return max_len

再……….咳咳

1052 爱生气的书店老板

  1. class Solution:
  2. def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
  3. # Step 1
  4. # 定义需要维护的变量,
  5. # 因为涉及求和所以定义sum_和max_sum, 同时需要知道老板什么时候'发动技能'，再定义一个max_start
  6. sum_, max_sum, max_start = 0, 0, 0
  7.       # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
  8.     start = 0
  9.     for end in range(len(customers)):
  10.         # Step 3
  11.         # 更新需要维护的变量 (sum_)
  12.         # 注意：这里只要当老板在当前时间点会发脾气的时候才维护
  13.         # sum_就不说了，和前面N道题的维护方法一样，新多出来的max_start也就是记录一样时间点而已，没什么fancy的
  14.         if grumpy[end] == 1:
  15.             sum_ += customers[end]
  16.         if sum_ > max_sum:
  17.             max_sum = sum_
  18.             max_start = start
  20.         # Step 4
  21.         # 根据题意可知窗口长度固定 (老板技能持续时间固定)，所以用if
  22.         # 窗口左指针前移一个单位保证窗口长度固定, 同时提前更新需要维护的变量 (sum_, max_avg)
  23.         if end >= minutes - 1:
  24.             if grumpy[start]:
  25.                 sum_ -= customers[start]
  26.             start += 1
  28.     # 这里对比其他题目多了一小步: 在找到老板发动技能的最大收益时间点(max_start)后
  29.     # 需要把受技能影响时间段中的grumpy全部置0 - 代表老板成功压制了自己的怒火
  30.     for i in range(max_start, max_start + minutes):
  31.         grumpy[i] = 0
  33.     # Step 5: 再遍历一遍数组求customer总数量并且返回结果
  34.     res = 0
  35.     for i in range(len(customers)):
  36.         if not grumpy[i]:
  37.             res += customers[i]
  38.     return res

一片寂静……

1423 可获得的最大点数

  1. class Solution:
  2. # 这题相比前面的题目加了一丢丢小的变通: 题目要求首尾串最大点数，其实就是求非首尾串的连续序列的最小点数
  3. def maxScore(self, cardPoints: List[int], k: int) -> int:
  4. # 特解
  5. n = len(cardPoints)
  6. if k == n:
  7. return sum(cardPoints)
  8.       # Step 1
  9.     # 定义需要维护的变量，因为涉及求和所以定义sum_和min_sum
  10.     m = n - k
  11.     sum_, min_sum = 0, math.inf
  13.     # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
  14.     start = 0
  15.     for end in range(n):
  16.         # Step 3
  17.         # 更新需要维护的变量 (sum_)
  18.         sum_ += cardPoints[end]
  20.         # Step 4
  21.         # 根据题意可知窗口长度固定，所以用if
  22.         # 窗口左指针前移一个单位保证窗口长度固定, 同时提前更新需要维护的变量 (min_sum， sum_)
  23.         if end >= m - 1:
  24.             min_sum = min(min_sum, sum_)
  25.             sum_ -= cardPoints[start]
  26.             start += 1
  27.     # Step 5: 返回答案 (总点数减去非首尾串的连续序列的最小点数就可以得到首尾串的最大点数)
  28.     return sum(cardPoints) - min_sum

1151 最少交换次数来组合所有的 1

  1. class Solution:
  2. def minSwaps(self, data: List[int]) -> int:
  3. # 先数出一共有多少个1，输出来的个数就是窗口的长度
  4. num_ones = 0
  5. for i in range(len(data)):
  6. if data[i] == 1:
  7. num_ones += 1
  8.       # Step 1
  9.     # 定义需要维护的变量，求最小swap次数其实就是求窗口中0个数的最小值，因此定义num_zeros, min_num_zeros
  10.     num_zeros, min_num_zeros = 0, math.inf
  12.     # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
  13.     start = 0
  14.     for end in range(len(data)):
  15.         # Step 3
  16.         # 更新需要维护的变量 (num_zeros， min_num_zeros)
  17.         if data[end] == 0:
  18.             num_zeros += 1
  19.         if end - start + 1 == num_ones:
  20.             min_num_zeros = min(min_num_zeros, num_zeros)
  22.         # Step 4
  23.         # 根据题意可知窗口长度固定 (数组1的总个数)，所以用if
  24.         # 窗口左指针前移一个单位保证窗口长度固定, 同时提前更新需要维护的变量 (num_zeros)
  25.         if end >= num_ones - 1:
  26.             if data[start] == 0:
  27.                 num_zeros -= 1
  28.             start += 1
  30.     # Step 5: 返回答案 (如果min_num_zeros依旧是math.inf说明数组没有1存在，不能swap，返回0即可)
  31.     if min_num_zeros == math.inf:
  32.         return 0
  33.     return min_num_zeros

OK……到目前为止，12道中等题全部结束。读者到此应该可以感觉到这12道题目其实就是遵循一个模子，沿用楼主share的思路只需要修改个别变量就可以全部秒杀！当然，模板只是对思路进行浓缩，楼主不建议大家硬背模板，而是建议先结合模板和几道样题，通过笔纸反复模拟出窗口的滑动过程去加深理解滑动窗口类型题目的共通之处。

作者：eason734 链接
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。