一、滑动窗口概述
滑动窗口，顾名思义就是一个可以滑动的窗口，它可以用来解决一些数组/字符串的子元素问题。
滑动窗口的核心思想是，定义一些指针和索引来表示一些位置，移动窗口，更新状态，并且在不遗漏任何位置的前提下，找到我们需要的答案。
那么，程序员在使用滑动窗口算法时，需要如何思考呢？
首先，一定是定义一个窗口，这个窗口通常是一个连续的子区间，然后用变量 left 和 right 表示窗口的左右边界，再根据问题的需要定义一些其它变量。然后，窗口开始向右滑动，当窗口右端点右移时，也就是 right += 1 时，窗口中多了一个右边的元素，窗口的和会发生什么变化？需要减少还是增加？这部分问题需要我们自己去思考。
二、常用滑动窗口算法题目及解法
1. 最小覆盖子串
题目描述：给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。
解法：使用双指针和哈希表。首先使用哈希表记录下字符串 T 中每个字符出现的次数，然后使用双指针 left 和 right 来表示窗口的左右边界。当窗口中包含所有字符时，取最小子串，然后左指针右移，不断更新最小字符串。当窗口中不包含所有字符时，右指针右移。
class Solution:
def minWindow(self, s: str, t: str) -> str:
if not s or not t:
return ""
left, right = 0, 0
cnt = len(t)
need = {}
for i in t:
need[i] = need.get(i, 0) + 1
res = ""
min_len = float("inf")
while right 0:
cnt -= 1
need[s[right]] -= 1
right += 1
while cnt == 0:
if (right - left) < min_len:
min_len = right - left
res = s[left:right]
if s[left] in need:
if need[s[left]] == 0:
cnt += 1
need[s[left]] += 1
left += 1
return res
2. 求和等于K的最长子数组
题目描述：给定一个整数数组 nums 和一个目标值 k，请找到数组中和等于 k 的最长子数组长度。如果不存在任意一个符合条件的子数组，则返回 0。
解法：使用前缀和加哈希表。首先，定义一个哈希表，存储每个前缀和出现的最早下标。然后，定义一个变量 sum 为前缀和，当 sum – k 在哈希表中存在时，说明从 i 到 j 存在一个子数组和等于 k，将其长度与之前计算的最大长度进行比较，更新答案。
class Solution:
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
if not nums:
return 0
res = 0
prefix_sum = 0
has_dict = {0:-1}
for i in range(len(nums)):
prefix_sum += nums[i]
if prefix_sum - k in has_dict:
res = max(res, i - has_dict[prefix_sum - k])
if prefix_sum not in has_dict:
has_dict[prefix_sum] = i
return res
三、滑动窗口要点总结
1、滑动窗口算法（双指针算法）是一种固定长度的窗口在数组上滑动，通过双指针（数组坐标）对数组一个个进行滑动统计，并得出问题的解。
2、滑动窗口的时间复杂度通常为 O(n)，比一般的暴力解法要高效许多。
3、当想要在一个数组或是一个字符串中找到一个子区间，滑动窗口算法应该是一个不错的选择。
4、在使用滑动窗口算法的过程中，一定要注意边界问题，并且稍加思考时，可以使用哈希表等数据结构优化算法。
5、掌握了滑动窗口算法的思想和模板，我们可以针对具体问题进行适当的修改和调整，解决更多的问题。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/151979.html
微信扫一扫 
支付宝扫一扫 