滑动窗口汇总

之前写过这一篇，同向双指针 和 滑动窗口 讲的是同向双指针。今天这个文章是面试经典 150 题中的滑动窗口专题，可以和上一篇文章互相补充。

滑动窗口

滑动窗口是一种常见的算法思想，用于解决数组和字符串相关的问题。其思想是通过两个指针来构造一个窗口，在满足特定条件的情况下，移动窗口的位置来求解问题。

一般情况下，滑动窗口的问题可以通过以下步骤解决：

1. 初始化窗口的左右边界（两个指针）；
2. 移动右指针扩大窗口，直到满足特定条件（例如满足子串包含某些字符或总和达到某个值）；
3. 移动左指针缩小窗口，直到不满足特定条件为止；
4. 记录最优解；
5. 重复步骤2-4，直到右指针到达数组的末尾。

滑动窗口可以用于求解一些经典问题，例如：最长无重复子串、最小覆盖子串、长度为k的最小子数组等。

在实际应用中，滑动窗口算法往往比暴力求解要快速和高效，因为滑动窗口只对每个元素进行一次处理，时间复杂度为O(n)。在处理数组和字符串问题时，如果发现可以使用滑动窗口思想，可以尝试使用滑动窗口来解决问题，提高代码的效率和可读性。

3. 无重复字符的最长子串 - 力扣（Leetcode）

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列， 不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

给出两种实现方法：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window = Counter()
        left,res = 0,0
        for right,c in enumerate(s):
            window[c] += 1
            while window[c] >1:
                window[s[left]] -= 1
                left += 1
            res = max(res,right-left+1)
        return res

具体来说，代码首先定义了一个字典 window，用于记录字符串 s 中每个字符出现的次数。然后定义了两个指针 left 和 right，分别表示窗口的左右边界。

接下来，代码遍历字符串 s 中的每个字符，将当前字符添加到 window 中，并检查是否有重复字符。如果有重复字符，就将 left 指针向右移动，直到没有重复字符为止。在这个过程中，代码不断更新 res 变量，用于记录最长的子串长度。

最终，代码返回 res 变量的值，即为最长的无重复字符子串的长度。

该代码的时间复杂度为 O(n)，其中 n 是字符串 s 的长度。因为代码只遍历了一次字符串 s，因此时间复杂度为线性级别。空间复杂度为 O(k)，其中 k 是字符集的大小，因为代码需要使用一个字典来记录每个字符出现的次数。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        maxLength = 0
        left=0
        for right,c in enumerate(s):
            while c in s[left:right]:
                left += 1
            maxLength = max(maxLength,right - left +1)
        return maxLength

这段代码实现了一个求最长无重复子串长度的算法，其思路是维护一个滑动窗口，滑动窗口的左右边界是 left 和 right，初始时 left = 0，right = -1。每次右移 right，将当前字符加入窗口中，然后检查窗口内是否有重复字符，如果有，左移 left 直到窗口内没有重复字符。维护一个 maxLength 变量记录最长无重复子串的长度，每次更新 maxLength。最终返回 maxLength。

这个算法的时间复杂度是 $O(n^2)$，其中 n 是字符串 s 的长度。因为在检查窗口内是否有重复字符的过程中，使用了 s[left:right] 这个切片操作，时间复杂度为 $O(right-left)$，最坏情况下 right - left 可能是 $O(n)$ 级别的，所以总的时间复杂度是 $O(n^2)$。如果使用哈希表来优化查重操作，可以将时间复杂度降到 $O(n)$。

209. 长度最小的子数组 - 力扣（Leetcode）

给定一个含有 n ****个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ****≥ target ****的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度 。 如果不存在符合条件的子数组，返回 0 。

示例 1：

输入： target = 7, nums = [2,3,1,2,4,3]
输出： 2
解释： 子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入： target = 4, nums = [1,4,4]
输出： 1

示例 3：

输入： target = 11, nums = [1,1,1,1,1,1,1,1]
输出： 0

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

进阶：

• 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        l = 0
        res = len(nums)+1
        s = 0 # 记录元素和
        for r,n in enumerate(nums):
            s += n
            while s >= target:
                res = min(res, r-l+1)
                s -= nums[l]
                l += 1
        return res if res < len(nums)+1 else 0

维护一个窗口，左右指针分别指向窗口的左右边界，当窗口内元素之和小于目标值 target 时，右指针向右移动扩大窗口，当窗口内元素之和大于等于目标值 target 时，记录窗口长度，并尝试将左指针向右移动缩小窗口。

具体实现步骤如下：

1. 初始化左指针 l = 0，记录结果 res = len(nums) + 1，表示当前还没有找到符合要求的子数组
2. 遍历数组，右指针 r 从 0 开始向右移动，计算当前窗口内元素之和 s
3. 当 s 大于等于目标值 target 时，更新结果 res 为 min(res, r-l+1)，表示找到一个符合要求的子数组，长度为 r-l+1，然后尝试将左指针向右移动缩小窗口，直到 s 小于目标值 target
4. 最后返回结果 res，如果 res 仍然等于 len(nums) + 1，表示没有找到符合要求的子数组，返回 0。

时间复杂度为 $O(n)$，其中 n 为数组的长度，因为只需要遍历一遍数组，每个元素最多被访问两次，因此时间复杂度为 $O(n)$。

这个进阶任务比较离谱，让你实现一个时间复杂度更高的。这是想让你写个前缀和+二分查找的。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:

        # 前缀和 + 二分
        n = len(nums)
        ans = n + 1
        sums = [0]
        for i in range(n):
            sums.append(sums[-1] + nums[i])
        
        for i in range(1, n + 1):
            targets = target + sums[i - 1]
            bound = bisect.bisect_left(sums, targets)
            if bound != len(sums):
                ans = min(ans, bound - (i - 1))
        
        return 0 if ans == n + 1 else ans

这个解法使用了前缀和和二分查找。具体来说，先计算出数组的前缀和 sums，其中 sums[i] 表示前 i 个元素的和。然后枚举子数组的左端点 i，令 targets = target + sums[i-1]，表示当前子数组要满足的和为 targets。接下来使用二分查找找到第一个位置 j，使得 sums[j] >= targets，那么对应的子数组就是 [i, j-1]，其长度为 j-i，更新最小长度即可。

时间复杂度为 O(n log n)，其中 n 为数组的长度。因为需要对每个元素进行一次二分查找，每次查找的时间复杂度为 log n，因此总时间复杂度为 O(n log n)。

30. 串联所有单词的子串 - 力扣（Leetcode）

给定一个字符串 s ****和一个字符串数组 words 。 words 中所有字符串 长度相同。

 s ****中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

• 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联字串在 s ****中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入： s = "barfoothefoobarman", words = ["foo","bar"]
输出： [0,9]
解释： 因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入： s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出： []
解释： 因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入： s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出： [6,9,12]
解释： 因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示：

• 1 <= s.length <= 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 和 s 由小写英文字母组成

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        w = Counter(words)
        res = []
        lenW = len(words[0])
        lenS = lenW*len(words)
        for i in range(len(s)):
            subW = dict.fromkeys(words,0)
            for j in range(i,i+lenS,lenW):
                if s[j:j+lenW] in subW:
                    subW[s[j:j+lenW]] += 1
            if subW == w:
                res.append(i)
        return res

具体实现如下：

1. 首先使用 collections.Counter 对 words 列表进行计数，得到一个字典 w，其中键是单词，值是单词在 words 中出现的次数。
2. 然后遍历字符串 s 中的每个字符，从当前位置开始尝试匹配包含所有单词的子串。
3. 对于每个可能的子串，创建一个字典 subW，键是单词，值是当前子串中该单词出现的次数。
4. 对于当前子串中的每个单词，如果该单词存在于 subW 中，则将其出现次数加 1。
5. 如果 subW 中的计数与 w 中的计数完全相同，则说明当前子串包含了 words 中所有单词，将其起始索引位置添加到结果列表中。
6. 最后返回结果列表。

时间复杂度为 $O(nm)$，其中 $n$ 是字符串 s 的长度，$m$ 是单词列表 words 的长度。每次遍历字符串需要判断 $m$ 个单词，时间复杂度为 $O(m)$。总共需要遍历字符串 $n-m+1$ 次，因此总时间复杂度为 $O(nm)$。空间复杂度为 $O(m)$，需要使用一个字典来存储单词计数。

76. 最小覆盖子串 - 力扣（Leetcode）

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

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入： s = "ADOBECODEBANC", t = "ABC"
输出： "BANC"
解释： 最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入： s = "a", t = "a"
输出： "a"
解释： 整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s 和 t 由英文字母组成

进阶： 你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        
        w = Counter(t)
        sub = defaultdict(int)
        res = ''
        l, r = 0, 0
        valid = 0
        while r < len(s):
            c = s[r]
            if c in w.keys():
                sub[c] += 1
                if sub[c] == w[c]:
                    valid += 1
            while valid == len(w):
                if not res or r - l < len(res):
                    res = s[l:r+1]
                d = s[l]
                if d in w.keys():
                    if sub[d] == w[d]:
                        valid -= 1
                    sub[d] -= 1
                l += 1
            r += 1
        return res

本文正在参加「」