力扣100题——子串

力扣100题——子串"/>

力扣100题——子串

560.和为k的子数组

这道题目不是滑动窗口的类型，因为长度并不是固定的。（好的，我在说废话）

注意题目要求是子数组，且是连贯的。那这里的话，解法有很多，最简单的就是暴力解法，但在这里我想说的是前缀和加哈希表优化，嘿嘿，适当的参考了一下官方的解题办法。ok,来。

首先什么是前缀和，先看个列子：

有个数组：nums=[1,2,3,4,5,6],那么他的前缀和就是0,1,3,6,10,15,21。

当i=0的时候，前缀和是0，

当i=1的时候，前缀和是1，

当i=2的时候，前缀和是0+1+2=3，以此类推。

我们已经知道了前缀和的值和k的值，那想求的是题目要求的连续子数组和为k的数，那是不是只要把当前的前缀和-k就可以得到连续的子数组的和，我们之前是用一个数组来表示的，那如果说得到的那个值出现在了这个数组中，是不是就说明找到了，上代码：

class Solution {public int subarraySum(int[] nums, int k) {int count=0,pre=0;//定义一个map，来存放各个前缀和出现的次数HashMap<Integer,Integer> mp=new HashMap<>();//这个主要是用以考虑连续数组只有一个的情况，比如说例子2中的3mp.put(0,1);for(int i=0;i<nums.length;i++){pre+=nums[i];if(mp.containsKey(pre-k)){count+=mp.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]
k=3
m=Solution.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]
k=3
m=Solution.maxSlidingWindow(nums,k)
print(m)

76.最小覆盖子串

思路：

这道题目的意思是要寻找s中覆盖t的连续最短子串，那我们可以用一个字典need来存储各个元素出现的次数，以及用needCnt来标识此时滑动窗口中的元素是否全部包括t中的元素，再用元组res来存储各个满足条件的窗口中的长度的下标。用i和j分别代表窗口的左边界和右边界，然后右移窗口，直到needCnt==0停止，这就代表着窗口中的元素已经全部包括t了，这里需要判断此时的元素出现的次数是否大于0，是的话长度得减1，减一和加一的标准是j++时，--，i++时，++。具体的大家看代码应该就能看懂了。加油！！！

代码：

class Solution:def minWindow(self, s: str, t: str) -> str:# 1.创建一个字典，用以存储各个字母出现的次数need=collections.defaultdict(int)# 循环遍历t数组，统计次数存入need中for c in t:need[c]+=1# 更新needCnt的值，此时就是t数组的长度，当其能匹配到S中相应的字符时，便减一直到为0needCnt=len(t)# 代表左边窗口i=0# 定义元组的大小，右边表示正无穷res=(0,float('inf'))# 循环遍历s数组for j,c in enumerate(s):#当s中的字符对应在字典中的值大于0时，needCnt--,因为只要是在右移的过程中，碰到的元素都是--的if need[c]>0:needCnt-=1need[c]-=1#当窗口中的元素的所有值都包含了t中的元素值之后，便开始移动左边窗口了if needCnt==0:while True:c=s[i]# 直到移动的元素是t中的，即need[c]==0,这里不考虑其他元素有没有可能为0的情况，因为如果为0，那就已经不在滑动窗口中了，目标元素在原始情况下是+1的，从此便区分开了if need[c]==0:breakneed[c]+=1i+=1#直到遇到t中元素的边界，这里就需要存储一下窗口大小，便于后续取出，之后便再次移动左边界，寻找遍历最短的包括t数组的连续数组if j-i<res[1]-res[0]:res=(i,j)need[s[i]]+=1needCnt+=1i+=1# 这里切片return '' if res[1]>len(s) else s[res[0]:res[1]+1]