0.4 子串

[560. 和为 K 的子数组](https://leetcode.cn/problems/subarray-sum-equals-k/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        pre_sum = 0
        res = 0
        dic = {0:1}
        for num in nums:
            pre_sum += num
            res += dic.get(pre_sum-k, 0)
            dic[pre_sum] = dic.get(pre_sum, 0) + 1
        return res
```
[239. 滑动窗口最大值](https://leetcode.cn/problems/sliding-window-maximum/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque()
        ans = []
        for i, item in enumerate(nums):
            while q and nums[q[-1]] <= item:
                q.pop()
            q.append(i)
            if i-q[0] + 1 > k:
                q.popleft()
            if i >= k-1:
                ans.append(nums[q[0]])
        return ans
```
[76. 最小覆盖子串](https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def judge(self, windows, needs):
        for k in needs.keys():
            if windows.get(k,0) < needs[k]:
                return False
        return True

def minWindow(self, s: str, t: str) -> str:
        windows = {}
        needs = {}
        for c in t:
            needs[c] = needs.get(c,0) + 1
        left = 0
        ans_left = -1
        ans_right = len(s)
        for right, item in enumerate(s):
            windows[item] = windows.get(item, 0) + 1
            while self.judge(windows, needs):
                if right - left < ans_right - ans_left:
                    ans_left = left
                    ans_right = right
                windows[s[left]] -= 1
                left += 1
        return '' if ans_left == -1 else s[ans_left:ans_right+1]
```