力扣hot100_子串_python版本

一、560. 和为 K 的子数组

• 思路：这就是一道典型的前缀和的题
• 代码:

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 

二、239. 滑动窗口最大值

• 思路1：暴力。这道题如果暴力求解其实很简单，根据描述写就行了，但是复杂度比较高，O(n2)O(n^2)O(n2)
• 代码

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步
  1. 入（元素入队尾，并维护单调性（看需要保持单增，还是单减））
  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]