网站建设市场调研报告,网络营销包括哪些策略,东莞做网站排名,网站采用什么方法建设209. 长度最小的子数组
这篇文章主要是想针对这题 209. 长度最小的子数组#xff0c;总结一下双指针或是滑动窗口的小细节。对于暴力算法#xff0c;我们就不再阐释了。
算法原理#xff1a;
滑动窗口主要是通过控制循环终止节点j#xff0c;并移动i来缩放窗口。具体而言…209. 长度最小的子数组
这篇文章主要是想针对这题 209. 长度最小的子数组总结一下双指针或是滑动窗口的小细节。对于暴力算法我们就不再阐释了。
算法原理
滑动窗口主要是通过控制循环终止节点j并移动i来缩放窗口。具体而言当大小为j - i 1的窗口内所有元素sumnums达到要求sumnums target的时候计算此时的长度是否是达到要求的最小长度 minlen min(minlen, j - i 1)。同时缩小窗口i 1继续判断此时的窗口内元素总和的大小。
代码呈现
这里我们使用了两种表示方法注意观察两者之间的区别。这里我们直接将最小长度minlen赋值为无穷大float(inf)。
方法一遍历了j当满足条件sumnums target缩小窗口。但是因为使用了if语句我们需要把j - 1,sumnums sumnums - nums[i] -nums[j]。原因是后面迭代了j 1且再一次经过条件j len(nums)时sumnums nums[j]。该做法相当于是把缩小后的窗口中总数值是否大于target的判断交给下一次迭代。
方法二该方法在需要缩小窗口的时候使用了while即在本次迭代中不断缩小窗口直到总和小于target进入下一次迭代。因为停留在本次迭代中j不变所以在while循环中不会涉及到j和nums[j]的变化。
两种方法本质上是一样的只是关于if和while的实现细节容易出错。可以使用target 5 nums [1, 1, 1, 1, 4]来作为例子试一试。
第一种
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) - int:minlen float(inf)sumnums 0i 0j0while j len(nums):sumnums nums[j]if sumnums target:minlen min(minlen, j - i 1)sumnums sumnums - nums[i] -nums[j]j - 1i 1j 1return minlen if minlen ! float(inf) else 0第二种
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) - int:minlen float(inf)sumnums 0i 0j0for j in range(len(nums)):sumnums nums[j]while sumnums target:minlen min(minlen, j - i 1)sumnums sumnums - nums[i]i 1return minlen if minlen ! float(inf) else 0904. 水果成篮
对于双指针方法我们举一反三。 904. 水果成篮
下面对题目进行文字的数学转化 题目中“要尽可能多地收集水果”表示滑动窗口的大小maxnums尽可能大。 “只有两个篮子并且每个篮子只能装单一类型的水果”表示len(basket) 2。每一次通过 if fruits[j] not in basket看看在不在篮子里。因为总量没有限制在就不管不在篮子里就加入篮子里。 “可以选择任意一棵树开始采摘” 表示滑动窗口左边界i可以随便移动。“每采摘一次你将会向右移动到下一棵树并继续采摘。” 表示滑动窗口从左往右移动是连续的。
注意 为了方便分析我们用basket表示篮子里面所装的水果种类record记录每一种水果种类有多少。为什么要使用record。就是当窗口需要缩小的时候fruit[i]类型的水果我们不知道在窗口中具体有多少个所以不能随意地将它pop出篮子。例如对于fruits [3,3,3,1,2,1,1,2,3,3,4]在选中basket [1, 2, 1, 1 ,2]为滑动窗口的时候此时fruit[j] 3我们需要将i 3向后挪一位fruit[i] 1但后面还要1种类的水果所以即使往后移动窗口篮子里面种类还是不变的。
代码如下
class Solution:def totalFruit(self, fruits: List[int]) - int:maxnums 0i 0basket [] # 篮子——basket里面只能有两种数字 len(basket) 2 record {} # 需要记录个数for j in range(len(fruits)):if fruits[j] not in basket:basket.append(fruits[j])record[fruits[j]] 1else:record[fruits[j]] 1while len(basket) 2:maxnums max(maxnums, j - i)if record[fruits[i]] 1: basket.pop(basket.index(fruits[i]))record[fruits[i]] 0else:record[fruits[i]] - 1i 1maxnums max(maxnums, j - i 1)return maxnums
值得一提的是record和basket可以合二为一使得代码更简单这里就不再赘述了。
后面接着整理双指针滑动窗口整理2——最小覆盖子串。
