一、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 ans = 0 cnt = defaultdict(int) for p in presum: ans += cnt[p - k] cnt[p] += 1 return ans
二、239. 滑动窗口最大值

- 思路1:暴力。这道题如果暴力求解其实很简单,根据描述写就行了,但是复杂度比较高,O(n2)O(n^2)O(n2)
- 代码
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: if len(nums) == 1: return nums res = [] left, right = 0, k while left <= (len(nums)-k): res.append(max(nums[left:right])) left+=1 right+=1 return res
- 思路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() 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 = 0 for right, word in enumerate(s): cntS[word] += 1 while cntS >= cntT: if right - left < ansRight - ansLeft: ansLeft, ansRight = left, right cntS[s[left]] -= 1 left += 1 return \"\" if ansLeft < 0 else s[ansLeft:ansRight+1]