滑动窗口思想(数组)

2023-06-05 15:37| 来源: 网络整理| 查看: 265

文章目录前言一、思想二、相关题目讲解1.长度最小的子数组(leetcode 209.)2.水果成篮(leetcode 904.)3.最小覆盖子串(leetcode 76.) 三、模拟行为螺旋矩阵II(leetcode.59)leetcode 54.螺旋矩阵剑指Offer 29. 顺时针打印矩阵总结

前言

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n2 )的暴力解法降为O(n)。主要要理解滑动窗口如何移动窗口起始位置，达到动态更新窗口大小的，从而得出长度最小的符合题目条件的长度。

一、思想

那么滑动窗口是如何用一个for循环来完成整个操作的呢？首先思考用一个for循环，那么应该表示滑动窗口的起始位置，还是终止位置。如果只用一个for循环来控制滑动窗口的起始位置，那么剩下的终止位置如何遍历？这就又回到了暴力解法。所以只用一个for循环的话，那么这个循环的索引，一定是表示滑动窗口的终止位置。那么滑动窗口的起始位置如何操作移动呢？实现滑动窗口，主要确定如下三点： (1) 窗口内是什么？ (2) 如何移动窗口的起始位置？ (3) 如何移动窗口的结束位置？窗口就是满足长度最小的符合题目条件的连续子数组。窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。在这里插入图片描述通过这个图例可以体会到滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n2 )暴力解法降为O(n)。

二、相关题目讲解 1.长度最小的子数组(leetcode 209.)

代码如下（示例）：

class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: l=len(nums) left=0 right=0 min_len=float('inf')#正无穷 cur_sum=0 for right in range(0,l): cur_sum += nums[right] while cur_sum >= target: # 当前累加值大于目标值 min_len = min(min_len, right - left + 1) cur_sum -= nums[left] left += 1 #移动滑动窗口起始位置 right += 1 #移动滑动窗口结束位置 return min_len if min_len != float('inf') else 0

时间复杂度是O(n)，有同学可能会问为什么不是O(n2 )呢，因为一个for循环下，虽然里面还放一个while循环，但是主要看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也依旧是O(n)。

2.水果成篮(leetcode 904.)

代码如下（示例）：

class Solution: def totalFruit(self, fruits: List[int]) -> int: l=len(fruits) left=0 res=0 classMap=defaultdict(int)# classCnt=0 for right in range(0,l): if classMap[fruits[right]]==0: classCnt+=1 classMap[fruits[right]]+=1 while classCnt>2: if classMap[fruits[left]]==1: classCnt-=1 classMap[fruits[left]]-=1 left+=1 #一旦满足条件，更新结果 res = max(res, right - left + 1) return res

本题区别于76题，这道题求的是最大滑窗，最大滑窗模版：给定数组 nums，定义滑窗的左右边界 left, right，求满足某个条件的滑窗的最大长度。关键的区别在于，最大滑窗是在迭代右移右边界的过程中更新结果，而最小滑窗是在迭代右移左边界的过程中更新结果。因此虽然都是滑窗，但是两者的模板和对应的贪心思路并不一样。

while right str: from collections import Counter#快速计数 template_dict=Counter(t)#统计目标字符串里各字符的个数 window_dict={}#定义了一个滑动窗口字典 for each_key in template_dict:#对于目标字符串的每个字符 if each_key not in window_dict:#如果不在滑动窗口里 window_dict[each_key]=0#就赋值为零 def isContains(cur_dict,tmp_dict): for each_key in tmp_dict: if cur_dict[each_key]end-start+1 min_len=end-start+1 res=s[start:end+1] if s[start] in window_dict: window_dict[s[start]]-=1 start+=1 return res

本题是最小滑窗思路，最小滑窗模板：给定数组 nums，定义滑窗的左右边界 left, right，求满足某个条件的滑窗的最小长度。滑动窗口简单说就是右指针先出发，左指针视情况追赶右指针。因此，右指针最多遍历一遍数组，左指针也最多遍历一次数组，时间复杂度不超过O(2N)。接下来，如何判断滑动窗口内是否满足题设条件，有两种选择：(1) 要么你遍历这个滑窗，通过遍历来断滑窗是否满足需要O(N), 那么总的时间就退化为O(N2), (2) 要么你选择字典，用空间换时间，那么判断划窗是否满足条件则需要 O(1)，总时间为O(N).

while right

【本文地址】

滑动窗口思想(数组)

滑动窗口思想(数组)

今日新闻

推荐新闻