之前写过这一篇，同向双指针 和 滑动窗口 讲的是同向双指针。今天这个文章是面试经典 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(n2)O(n^2)，其间 n 是字符串 s 的长度。由于在查看窗口内是否有重复字符的过程中，运用了 s[left:right] 这个切片操作，时刻复杂度为 O(right−left)O(right – left)，最坏情况下 right – left 可能是 O(n)O(n) 等级的，所以总的时刻复杂度是 O(n2)O(n^2)。假如运用哈希表来优化查重操作，能够将时刻复杂度降到 O(n)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)O(n)，其间 n 为数组的长度，由于只需求遍历一遍数组，每个元素最多被访问两次，因而时刻复杂度为 O(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)O(nm)，其间 nn 是字符串 s 的长度，mm 是单词列表 words 的长度。每次遍历字符串需求判断 mm 个单词，时刻复杂度为 O(m)O(m)。总共需求遍历字符串 n−m+1n-m+1 次，因而总时刻复杂度为 O(nm)O(nm)。空间复杂度为 O(m)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

该函数完成了在字符串 s 中找到包括字符串 t 中一切字符的最短子串。该函数运用了滑动窗口算法。

算法过程：

  1. 首要运用 Counter 函数计算字符串 t 中每个字符的呈现次数。

  2. 界说一个 defaultdict，用于存储字符串 s 中每个字符呈现的次数。

  3. 界说指针 l 和 r，表明滑动窗口的左右鸿沟，初始值都为 0。

  4. 界说一个计数器 valid，表明滑动窗口中已经包括字符串 t 中字符的个数。初始值为 0。

  5. 遍历字符串 s 中每个字符，假如该字符在字符串 t 中呈现，则将该字符呈现次数加 1。

  6. 假如该字符呈现次数等于字符串 t 中该字符的呈现次数，则 valid 计数器加 1。

  7. 假如 valid 等于字符串 t 中字符的个数，阐明滑动窗口中已经包括了字符串 t 中的一切字符。此刻记载当时滑动窗口的长度，并与之前的成果进行比较，假如更短，则更新成果字符串。

  8. 移动滑动窗口的左鸿沟 l，假如左鸿沟字符呈现在字符串 t 中，则将该字符呈现次数减 1，假如该字符呈现次数减 1 后等于字符串 t 中该字符的呈现次数，则 valid 计数器减 1。

  9. 重复过程 5-8，直到遍历完整个字符串 s。

  10. 回来成果字符串。

时刻复杂度为 O(∣s∣+∣t∣)O(|s|+|t|)，空间复杂度为 O(∣t∣)O(|t|)。

本文正在参加「金石方案」