一、560. 和為 K 的子數組

• 思路：這就是一道典型的前綴和的題
• 代碼:

class Solution:def subarraySum(self, nums: List[int], k: int) -> int:presum = [0] * (len(nums) + 1)for i, x in enumerate(nums):presum[i + 1] = presum[i] + x  # 前綴和序列需要n+1個ans = 0cnt = defaultdict(int)for p in presum:ans += cnt[p - k]cnt[p] += 1return ans

二、239. 滑動窗口最大值

• 思路1：暴力。這道題如果暴力求解其實很簡單，根據描述寫就行了，但是復雜度比較高，$O(n^2)$
• 代碼

class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:if len(nums) == 1:return numsres = []left, right = 0, kwhile left <= (len(nums)-k):res.append(max(nums[left:right]))left+=1right+=1return res

• 思路2：單調隊列。單調隊列分為3步
  1. 入（元素入隊尾，并維護單調性（看需要保持單增，還是單減））
  2. 出（元素離開隊首）
  3. 記錄答案
• 代碼

class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:ans = []q = deque()for i, x in enumerate(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()這玩兒意可以比較，當然如果沒法比較也可以自己寫一個比較函數
• 代碼：

class Solution:def minWindow(self, s, t):ansLeft, ansRight = -1, len(s)cntS = Counter()cntT = Counter(t)left = 0for right, word in enumerate(s):cntS[word] += 1while cntS >= cntT:if right - left < ansRight - ansLeft:ansLeft, ansRight = left, rightcntS[s[left]] -= 1left += 1return "" if ansLeft < 0 else s[ansLeft:ansRight+1]