Leetcode 76. 最小覆盖子串

心路历程：

这道题一开始以为要用动态规划来解，但是结合题目中需要返回的是最短子串本身而不是长度，因此在对于字符串s建模时至少需要维护i和j两个变量，再加上这道题没有明显的递推。

这道题是滑动窗口双指针经典问题。
a. fast指针的更新规则：向右移动直到窗口包含了所有t中的元素。
b. slow指针更新规则：向右移动直到窗口内元素’刚好‘满足t中元素。
c. slow驱动下一次fast更新的规则：slow指针’多‘移动一位，使得当前元素又不满足fast停下的规则了，同时让fast加1。
重复上述三个步骤直到fast或者slow都到头。

双指针的核心还是在于在while循环中确定双指针的更新规律。

注意的点：

1、这道题的难点在于边界条件，需要让fast指针停在刚好满足条件的地方，然后再用slow驱动fast
2、需要明确fast移动的条件(不满足元素要求)和slow移动的条件(满足元素要求删除冗余)

解法：双指针+滑动窗口+哈希表

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 这道题动态规划不好做，因为1、题目返回的是一个字符串而不是长度 2、t字符串本质是集合，难以转化为hashable的表达形式
        # 双指针 滑动窗口
        # 注意滑动窗口需要 滑动才行，不是静止窗口
        from collections import Counter
        n = len(s)
        fast, slow = 0, 0
        target = Counter(t)
        redunt = {eve:0 for eve in target.keys()}
        target_len = len(t)

        ans = [0, n+1]
        while fast < n and slow < n:
            # print(fast, slow, redunt, target_len, target)
            if target_len != 0:  # 扩张
                if s[fast] in t:
                    if target[s[fast]] != 0:
                        target[s[fast]] -= 1
                        target_len -= 1
                    else:
                        redunt[s[fast]] += 1
                if target_len != 0:
                    fast += 1  # 否则让fast停在当前位置
            else:  # 收缩
                if s[slow] in t:
                    if redunt[s[slow]] != 0:
                        redunt[s[slow]] -= 1
                    else:  # 此时找到了一个结果
                        target[s[slow]] += 1
                        target_len += 1
                        # print(target_len)
                        if fast - slow + 1 < ans[1] - ans[0]:  # 记录结果
                            ans = [slow, fast+1]
                        fast += 1  # 防止fast重复记录，驱动fast指针+1
                slow += 1  # 找到结果时slow依然+1使得原fast维护的结果不再满足题意

        if ans[1] == n + 1:
            return ''
        else:
            return s[ans[0]: ans[1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41