> 技术文档 > 力扣hot100_子串_python版本_力扣hot100 csdn python 算法 小橘子

力扣hot100_子串_python版本_力扣hot100 csdn python 算法 小橘子


一、560. 和为 K 的子数组

力扣hot100_子串_python版本_力扣hot100 csdn python 算法 小橘子

  • 思路:这就是一道典型的前缀和的题
  • 代码:
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 = 0 cnt = defaultdict(int) for p in presum: ans += cnt[p - k] cnt[p] += 1 return ans

二、239. 滑动窗口最大值

力扣hot100_子串_python版本_力扣hot100 csdn python 算法 小橘子

  • 思路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步
    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. 最小覆盖子串

力扣hot100_子串_python版本_力扣hot100 csdn python 算法 小橘子

  • 思路:这里很神奇,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]