python3-算法刷题-数组-滑动窗口-更新中

参考：https://labuladong.github.io/algo/2/20/27/

---

滑窗思路

1. 使用双指针，left = right = 0，把 [left, right) 称为窗口。最开始[0, 0)是没有元素的
2. 先不断增加right，直到窗口内数据达到某条件
3. 此时转而增加left，以缩小窗口，直到窗口内数据不再符合某条件
4. 重复直到right到达结尾
   第2步相当于寻找可行解，第3步是优化可行解，最后找到最优。

【困难】76.最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

思路：

【中等】567. 字符串的排列

https://leetcode.cn/problems/permutation-in-string/
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：
输入：s1 = “ab” s2 = “eidbaooo”
输出：true
提示：s1 和 s2 仅包含小写字母

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        left = 0
        right = 0
        valid = 0 # 记录符合条件的字符数目
        need = dict()
        for c in s1: # 初始化need字典
            if c in need: need[c] += 1
            else: need[c] = 1
        window = dict() # window计算的是滑窗里字符的个数
        while right < len(s2):
            c = s2[right] 
            right += 1 # 加入一个元素
            if c in need:
                # 更新window字典
                if c in window: window[c] += 1
                else: window[c] = 1
                # 判断当前的字符是否符合要求
                if window[c] == need[c]:
                    valid += 1
            # 判断是否需要收缩
            while right - left >= len(s1):
                # 此时所有字符都有且数量对
                if valid == len(need): 
                    return True
                # 缩小窗口
                d = s2[left]
                left += 1
                # 此时左端一定在window中
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        return False

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

219. 存在重复元素 II

https://leetcode.cn/problems/contains-duplicate-ii/
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：
输入：nums = [1,2,3,1], k = 3
输出：true

示例 2：
输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：
输入：nums = [1,2,3,1,2,3], k = 2
输出：false

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        pos = {}
        for i, num in enumerate(nums):
            if num in pos and i - pos[num] <= k:
                return True
            pos[num] = i
        return False
1
2
3
4
5
6
7
8