classSolution:defsubarraySum(self, nums: List[int], k:int)->int: presum =[0]*(len(nums)+1)for i, x inenumerate(nums): presum[i +1]= presum[i]+ x # 前缀和序列需要n+1个 ans =0 cnt = defaultdict(int)for p in presum: ans += cnt[p - k] cnt[p]+=1return ans
classSolution:defmaxSlidingWindow(self, nums: List[int], k:int)-> List[int]:iflen(nums)==1:return nums res =[] left, right =0, k while left <=(len(nums)-k): res.append(max(nums[left:right])) left+=1 right+=1return res
思路2：单调队列。单调队列分为3步
入（元素入队尾，并维护单调性（看需要保持单增，还是单减））
出（元素离开队首）
记录答案
代码
classSolution:defmaxSlidingWindow(self, nums: List[int], k:int)-> List[int]: ans =[] q = deque()for i, x inenumerate(nums):# 入while q and nums[q[-1]]<= x: q.pop()# 删除比x小的元素（找最大值，比x小的就不用看了） q.append(i)# 加入到队尾（这个队列也是单调的了）# 出if i - q[0]>= k:# 队首需要离开了（滑窗滑过了） q.popleft()# 记录if i >= k -1: ans.append(nums[q[0]]) retrun ans
三、76. 最小覆盖子串
思路：这里很神奇，Counter()这玩儿意可以比较，当然如果没法比较也可以自己写一个比较函数
代码：
classSolution:defminWindow(self, s, t): ansLeft, ansRight =-1,len(s) cntS = Counter() cntT = Counter(t) left =0for right, word inenumerate(s): cntS[word]+=1while cntS >= cntT:if right - left < ansRight - ansLeft: ansLeft, ansRight = left, right cntS[s[left]]-=1 left +=1return""if ansLeft <0else s[ansLeft:ansRight+1]
