网站维护专业,梦创义网站建设公司,4399网页游戏在线玩,河北seo基础入门教程560.和为k的子数组
这道题目不是滑动窗口的类型#xff0c;因为长度并不是固定的。#xff08;好的#xff0c;我在说废话#xff09; 注意题目要求是子数组#xff0c;且是连贯的。那这里的话#xff0c;解法有很多#xff0c;最简单的就是暴力解法#xff0c;但在这…560.和为k的子数组
这道题目不是滑动窗口的类型因为长度并不是固定的。好的我在说废话 注意题目要求是子数组且是连贯的。那这里的话解法有很多最简单的就是暴力解法但在这里我想说的是前缀和加哈希表优化嘿嘿适当的参考了一下官方的解题办法。ok,来。
首先什么是前缀和先看个列子
有个数组nums[1,2,3,4,5,6],那么他的前缀和就是0,1,3,6,10,15,21。
当i0的时候前缀和是0
当i1的时候前缀和是1
当i2的时候前缀和是0123以此类推。
我们已经知道了前缀和的值和k的值那想求的是题目要求的连续子数组和为k的数那是不是只要把当前的前缀和-k就可以得到连续的子数组的和我们之前是用一个数组来表示的那如果说得到的那个值出现在了这个数组中是不是就说明找到了上代码
class Solution {public int subarraySum(int[] nums, int k) {int count0,pre0;//定义一个map来存放各个前缀和出现的次数HashMapInteger,Integer mpnew HashMap();//这个主要是用以考虑连续数组只有一个的情况比如说例子2中的3mp.put(0,1);for(int i0;inums.length;i){prenums[i];if(mp.containsKey(pre-k)){countmp.get(pre-k);}mp.put(pre,mp.getOrDefault(pre,0)1);}return count;}
}
239、滑动窗口最大值 题解这道题用了一个优先队列。在优先队列里面的元素是已经排列好的。要注意的是用C和Python是不一样的。前者是默认从高到低对数组进行排列而后者是从低到高所以用python的时候需要注意要对其取负值。
解题思路用优先队列定义一个优先队列然后将前面的k值放入队列中将最大的那个元素存入数组中接着利用for循环从k值开始将新元素放入队中同时判断当前窗口中最大值是否在i-k中如果不是则需要弹出
纠结点
1.就是用while循环弹出的是一系列吗存在的意义是什么。
while循环的目的在于弹出窗口中最大的元素但要注意前提条件。如果此时窗口滑到了[-1,-1,-2]那前面所有大于这个窗口里面的最大值都要出队pop掉看个例子吧我放个代码看看就懂了。
import heapq
class Solution:def maxSlidingWindow(nums, k):n len(nums)# 注意 Python 默认的优先队列是小根堆q [(-nums[i], i) for i in range(k)]#这里的作用是将其调整成为一个大根堆,q本身就发生了改变,并返回noneheapq.heapify(q)ans [-q[0][0]]for i in range(k, n):heapq.heappush(q, (-nums[i], i))while q[0][1] i - k:# print(当前的k,i:,k,i)print(弹出的q值为,q[0][0])#将q对列中弹出最小的元素heapq.heappop(q)# print(弹出之后的q值,q)ans.append(-q[0][0])print(q2的值为, q)return ans
nums[1,0,-1,-3,5,3,6,7,9,10,-1,-1,-2,-3,3,2,3,1]
nums1[1]
k3
mSolution.maxSlidingWindow(nums,k)
print(m)
2.python代码的误解
heapq.heappop(q)这串代码的意思是弹出q中最小的元素所以print(q)是输出q这个队列里面的所有元素而不只是队列中最大的元素
3、当窗口右移时只需要判断最大值是否在滑动窗口中。所以说如果此时通过右移添加的元素是大于之前窗口中的最大值的这种情况下此时while循环里面它的最大值就是当前元素比较的下标也是当前元素的。所以就不要纠结为什么之前窗口最大的无法弹出了因为它遇见了一个比它更大的懂了吧。
下面的代码是我在pycharm编译器里面测试编写的若要放在力扣上面的话记得改动一下。
代码
import heapq
class Solution:def maxSlidingWindow(nums, k):n len(nums)# 注意 Python 默认的优先队列是小根堆q [(-nums[i], i) for i in range(k)]#这里的作用是将其调整成为一个大根堆,q本身就发生了改变,并返回noneheapq.heapify(q)ans [-q[0][0]]for i in range(k, n):heapq.heappush(q, (-nums[i], i))while q[0][1] i - k:print(此时的i,k,q[0][1]分别为,i,k,q[0][1])print(弹出的q值为,q[0][0])#将q对列中弹出最小的元素heapq.heappop(q)print(弹出之后的q值,q)ans.append(-q[0][0])print(q2的值为, q)return ans
nums[1,0,-1,-3,5,3,6,7]
nums1[1]
k3
mSolution.maxSlidingWindow(nums,k)
print(m)
76.最小覆盖子串
思路
这道题目的意思是要寻找s中覆盖t的连续最短子串那我们可以用一个字典need来存储各个元素出现的次数以及用needCnt来标识此时滑动窗口中的元素是否全部包括t中的元素再用元组res来存储各个满足条件的窗口中的长度的下标。用i和j分别代表窗口的左边界和右边界然后右移窗口直到needCnt0停止这就代表着窗口中的元素已经全部包括t了这里需要判断此时的元素出现的次数是否大于0是的话长度得减1减一和加一的标准是j时--i时。具体的大家看代码应该就能看懂了。加油
代码
class Solution:def minWindow(self, s: str, t: str) - str:# 1.创建一个字典用以存储各个字母出现的次数needcollections.defaultdict(int)# 循环遍历t数组统计次数存入need中for c in t:need[c]1# 更新needCnt的值此时就是t数组的长度当其能匹配到S中相应的字符时便减一直到为0needCntlen(t)# 代表左边窗口i0# 定义元组的大小右边表示正无穷res(0,float(inf))# 循环遍历s数组for j,c in enumerate(s):#当s中的字符对应在字典中的值大于0时needCnt--,因为只要是在右移的过程中碰到的元素都是--的if need[c]0:needCnt-1need[c]-1#当窗口中的元素的所有值都包含了t中的元素值之后便开始移动左边窗口了if needCnt0:while True:cs[i]# 直到移动的元素是t中的即need[c]0,这里不考虑其他元素有没有可能为0的情况因为如果为0那就已经不在滑动窗口中了目标元素在原始情况下是1的从此便区分开了if need[c]0:breakneed[c]1i1#直到遇到t中元素的边界这里就需要存储一下窗口大小便于后续取出之后便再次移动左边界寻找遍历最短的包括t数组的连续数组if j-ires[1]-res[0]:res(i,j)need[s[i]]1needCnt1i1# 这里切片return if res[1]len(s) else s[res[0]:res[1]1]
