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中的3
mp.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本身就发生了改变,并返回none
heapq.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本身就发生了改变,并返回none
heapq.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中相应的字符时，便减一直到为0
needCnt=len(t)
# 代表左边窗口
i=0
# 定义元组的大小，右边表示正无穷
res=(0,float('inf'))
# 循环遍历s数组
for j,c in enumerate(s):
#当s中的字符对应在字典中的值大于0时，needCnt--,因为只要是在右移的过程中，碰到的元素都是--的
if need[c]>0:
needCnt-=1
need[c]-=1
#当窗口中的元素的所有值都包含了t中的元素值之后，便开始移动左边窗口了
if needCnt==0:
while True:
c=s[i]
# 直到移动的元素是t中的，即need[c]==0,这里不考虑其他元素有没有可能为0的情况，因为如果为0，那就已经不在滑动窗口中了，目标元素在原始情况下是+1的，从此便区分开了
if need[c]==0:
break
need[c]+=1
i+=1
#直到遇到t中元素的边界，这里就需要存储一下窗口大小，便于后续取出，之后便再次移动左边界，寻找遍历最短的包括t数组的连续数组
if j-i<res[1]-res[0]:
res=(i,j)
need[s[i]]+=1
needCnt+=1
i+=1
# 这里切片
return '' if res[1]>len(s) else s[res[0]:res[1]+1]
