力扣100题-子串

1.和为K的子数组

• 描述：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

  子数组是数组中元素的连续非空序列。

思路一：

• 连续序列加上求和，自然而然想到使用前缀和，由于数可能是正0负，求子数组的个数，可以依赖于哈希表，遍历前缀和数组，通过-k去找之前是否出现过sj-k的前缀和数字，就相当于有多少个区间是满足条件的。以O[N]的复杂度解决了区间的查找，很巧妙。还有当只有一个元素的数组就这一个元素满足条件时，cnt[0] = 1是很重要的初始化。
• 代码

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        sum = [0]*(n+1)
        for i in range(n):
            sum[i+1] = sum[i] + nums[i] # 求前缀和数组
        cnt = defaultdict(int) # cnt初始化为0
        ans = 0
        for sj in sum:
            ans += cnt[sj - k] #先求解，再把数放进哈希表
            cnt[sj] += 1
        return ans

2.滑动窗口的最大值

• 描述：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

  返回 滑动窗口中的最大值 。

思路一：

• 优先队列，要求滑动窗口内的最大值，考虑快速可以排序的结构，即优先队列，每次移动，需要考虑当前的最大值是否在合法范围内，时间复杂度为o[NlogN]
• 代码：

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = [(-nums[i], i) for i in range(k)] # python默认小根堆，所以要存负数
        heapq.heapify(q) # 小根堆初始化
        ans = list()
        ans.append(-q[0][0])

        for i in range(k, n):
            heapq.heappush(q, (-nums[i], i))
            while q[0][1] <= i - k: # 使最大值要在合法范围内
                heapq.heappop(q)
            ans.append(-q[0][0])
        return ans

思路二：

• 单调队列。使用优先队列时，每个数字都要反复参加多次排序。如果nums[i] < nums[j]且i<j，那么nums[i]其实肯定不会成为答案，可以直接删掉。也就是说可以维护一个严格递减的队列来实现快速找最大值。由于队列队首可能会出队，队尾要入队，所以采取双向队列。
• 代码

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = collections.deque() # 双向队列初始化
        for i in range(k): # 先对第一个窗口初始化
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i) 
        ans = [nums[q[0]]]
        for i in range(k, n):
            while q and nums[i] >= nums[q[-1]]: # 淘汰之前的小于等于当前的数
                q.pop()
            q.append(i)
            while q[0] <= i - k:# 使队首在合法范围内
                q.popleft()
            ans.append(nums[q[0]])
        return ans

思路三：

• 分块，把整个数组以k为单位进行分组，那么对于每个窗口的起始位置i，它的一般情况会横跨两个区间，可以分别设置两个数组prefixMax和suffixMax来存储当前下标在块内的前置和后置的最大值，实现复杂度为O[N]。那么对于起始位置i的窗口内的最大值就是suffixMax[i]和prefixMax[i+k-1]中的较大值
• 代码：

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        prefixMax, suffixMax = [0]*n, [0]*n
        # 初始化前缀和和后缀和数组，考虑前后的边界情况
        for i in range(n):
            if i % k == 0:
                prefixMax[i] = nums[i]
            else:
                prefixMax[i] = max(prefixMax[i-1], nums[i])
        for i in range(n-1, -1, -1):
            if i == n-1 or (i+1) % k == 0:
                suffixMax[i] = nums[i]
            else:
                suffixMax[i] = max(suffixMax[i+1], nums[i])

        ans = list()
        for i in range(n-k+1):
            ans.append(max(suffixMax[i], prefixMax[i+k-1]))
        return ans

3.最小覆盖子串

• 描述：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

思路一：

• 双指针，先固定左指针，遍历移动右指针直到满足涵盖t,(判断涵盖通过Counter函数比较实现)，一旦实现，就移动左指针来尽可能地缩小子串范围。
• 代码：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        n = len(s)
        m = len(t)
        cnt_s = Counter()
        cnt_t = Counter(t) #字母出现次数计数器
        l = 0
        ans_left, ans_right = -1, n
        for r, c in enumerate(s):
            cnt_s[c] += 1
            while cnt_s >= cnt_t: # 出现合法子串，进而缩左端点
                if r - l < ans_right - ans_left:
                    ans_left, ans_right = l, r 
                cnt_s[s[l]] -= 1
                l += 1
        if ans_left == -1: #从未更新过答案，直接返回空字符串
            return ""
        return s[ans_left: ans_right + 1]

小节：

• 子串的应用范围还是比较广的，主要是要求连续，那么会跟前缀数组后缀数组，双指针这些联系比较紧密
• 分析题目的限制条件，寻找合理的结构或者算法取贪心解决，降低时间复杂度