力扣热题100——子串

和为 K 的子数组

560. 和为 K 的子数组

思路

如何快速求出区间[l,r]的和？

• 用前缀和：sum[l,r] = sum[r,1] - sum[l-1,1]

暴力思路很简单，枚举所有的区间即可，那么如何优化？

• 我们从第一个数开始枚举，枚举到第i个数。我们想知道1~i有多少个区间满足和为k。
• 设这样的区间为x，那么sum[i,1] - x = k, x = sum[i,1] -k。所以我们只需要统计1~i有多少个前缀和为x 的区间即可！

代码

class Solution:def subarraySum(self, nums: List[int], k: int) -> int:n = len(nums)sum_=0mp = defaultdict(int)mp[0] = 1ans=0 for num in nums:sum_+=numx = sum_ - kif x in mp:ans+=mp[x]mp[sum_]+=1return ans    

239. 滑动窗口最大值

239. 滑动窗口最大值

思路

滑动窗口板子题，求窗口的最大最小值，这里只简单说一下。

1. 我们使用滑动窗口维护一个单减序列，那么队首肯定就是这个窗口的最大值。
2. 有人想问，那么同时是否这个窗口的队尾就是最小值？答案不是，比如序列1 2 3 4 5, 窗口大小为3, 维护一个单调递减序列，是无法正确使得队尾就是最小值。
3. 所以我们想求最大值，就维护一个单减序列，队首就是最大值。想求最小值，就维护一个单增序列，队首就是最小值。

代码

class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:n = len(nums)dq = [0] * (n+9)hh=1tt=0ans = []for i in range(n):while hh <=tt and i-dq[hh]+1>k:hh+=1while hh <= tt and nums[dq[tt]] < nums[i]:tt-=1tt+=1dq[tt] = iif i >=k-1:ans.append(nums[dq[hh]])return ans

最小覆盖子串

76. 最小覆盖子串

思路

字符由英文字母组成，那么我们还是使用两个哈希表来判断这个子串是否覆盖了字符串t

1. 双指针维护一个滑动窗口，右指针一直往前。如果当前这个字符在t中出现过，那么记录下来，并且检查是否已经覆盖。如果覆盖了，那么移动左指针往前移动，直到没有覆盖。这个过程记录最小值
2. 如果不在字符串t 中出现过，那么跳过不处理。

代码

class Solution:def minWindow(self, s: str, t: str) -> str:def check(mp, mp2):for ch in range(100):x = ch-ord('A')if mp2[x]<mp[x]:return Falsereturn Truemp = [0]*100 # 字符串t中的标记mp2 = [0]*100for ch in t:mp[ord(ch)-ord('A')]+=1j = 0 ans_l, ans_r = -1, len(s)for i in range(len(s)):x = ord(s[i]) - ord('A')if mp[x]:mp2[x]+=1while check(mp, mp2):# print("def")if i-j < ans_r-ans_l:ans_l, ans_r = j,iif mp2[ord(s[j])-ord('A')]:mp2[ord(s[j])-ord('A')]-=1j+=1if ans_l!=-1:return s[ans_l:ans_r+1]else :return ""