Leetcode刷题笔记——滑动窗口篇

素材来自网络

链表子串数组题，用双指针别犹豫。
双指针家三兄弟，各个都是万人迷。
快慢指针最神奇，链表操作无压力。
归并排序找中点，链表成环搞判定。
左右指针最常见，左右两端相向行。
反转数组要靠它，二分搜索是弟弟。
滑动窗口老猛男，子串问题全靠它
左右指针滑窗口，一前一后齐头进
自诩十年老司机，怎料农村道路滑。
一不小心滑到了，鼻青脸肿少颗牙。
算法思想很简单，出了bug想升天

第一题: 最大连续1的个数

Leetcode485:最大连续1的个数：简单题 （详情点击链接见原题）

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数

python代码解法:

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        left, right, res = 0, 0, 0
        while right < len(nums):
            if nums[right] == 1:
                right += 1
            else:
                left = right    # 左指针和右指针指向同一个位置
                left += 1
                right += 1
            res = max(res, right - left)
        return res

第二题:子数组的最大平均数I

Leetcode643:子数组的最大平均数I：简单题 （详情点击链接见原题）

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

python代码解法:

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        left, right = 0, 0
        slide_total = 0
        max_average = -float('inf')
        while right < len(nums):
            slide_total += nums[right]
            right += 1
            while right - left >= k:
                max_average = max(max_average, slide_total / k)

                slide_total = slide_total - nums[left]
                left += 1
        return max_average

第三题:最长和谐子序列

Leetcode594. 最长和谐子序列：简单题 （详情点击链接见原题）

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度

python代码解法:

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return 0
        nums.sort()
        left, right = 0, 0
        ans = 0
        while right < len(nums):
            if nums[right] - nums[left] > 1:
                left += 1
            if nums[right] - nums[left] == 1:
                ans = max(ans, right - left + 1)
            right += 1
        return ans

第四题:长度最小的子数组

Leetcode209:长度最小的子数组：中等题 （详情点击链接见原题）

给定一个含有 n 个正整数的数组和一个正整数 target
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0

python代码解法:

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        total = 0
        left, right = 0, 0
        res = float('inf')  # res用来保存连续子数组的最短长度
        if sum(nums) < target:
            return 0
        while right < len(nums):
            total += nums[right]
            while total >= target:
                res = min(res, right - left + 1)
                total -= nums[left]
                left += 1

            right += 1
        return res

第五题:最大连续1的个数III

Leetcode1004:最大连续1的个数III：中等题 （详情点击链接见原题）

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数

python代码解法:

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left, right = 0, 0
        res = 0
        while right < len(nums):
            if nums[right] == 0:
                k -= 1
            while k < 0:
                if nums[left] == 0:		# 当将左指针指向的 0 移出滑动窗口时
                    k += 1
                left += 1
            res = max(res, right - left + 1)
            right += 1
        return res

第六题:替换后的最长重复字符

Leetcode424. 替换后的最长重复字符 / Leetcode2024. 考试的最大困扰度：中等题 （详情点击链接见原题）

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

如果K = 0，本题就变成了求解字符串中最长连续子串长度的问题
如果K > 0，则变成了允许我们变换子串中的 K 个字符能够变成一个连续串
historyCharMax保存滑动窗口内相同字母出现次数的历史最大值，通过判断滑动窗口宽度 right - left + 1是否大于 historyCharMax + K 来决定窗口是否做滑动，否则窗口就扩张

问题的关键在于如何判断一个字符串改变 K 个字符能够变成一个连续串，如果当前窗口中 出现次数最多的字符个数 + K 大于串长度，则窗口扩张，否则窗口收缩
当窗口触达字符串末尾时,运算结束，窗口宽度为最终结果

核心要点：

1. count 记录的是窗口里字符出现的次数，是窗口里的，所以左窗口右移后，记得将移出去的元素个数 -1
2. 我们的目的就是让窗口尽可能的扩张，有 k 个字符的容错机会，容错机会肯定要用给 count 中出现次数最多的字符才有机会让窗口扩张
3. 就算某一时刻发现框里元素都不一样，但不要怀疑，因为它曾经辉煌过，他会一直呈现窗口最大时的状态

python代码解法:

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left, right = 0, 0
        count = Counter()
        historyCharMax = 0
        while right < len(s):
            count[s[right]] += 1
            historyCharMax = max(historyCharMax, count[s[right]])
            if right - left + 1 > historyCharMax + k:  # 如果当前窗口的大小比历史窗口中出现次数最多的字母次数 + k 还大,证明k不足以将当前窗口全部替换成同一个字母，所以窗口左移
                count[s[left]] -= 1
                left += 1
            right += 1
        return right - left

这题的难点不同于一般的滑窗，这里滑窗内部的元素不一定满足条件，即滑窗没有被维护，historyCharMax 并不是当前窗口内出现次数最多字母的次数，而是历史窗口中出现次数最多字母的次数

第七题:尽可能使字符串相等

Leetcode1208:尽可能使字符串相等：中等题 （详情点击链接见原题）

给你两个长度相同的字符串，s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值

python代码解法:

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        left, right = 0, 0
        ans = 0
        while right < len(s):
            maxCost -= abs(ord(s[right]) - ord(t[right]))
            while maxCost < 0:
                maxCost += abs(ord(s[left]) - ord(t[left]))
                left += 1
            ans = max(ans, right - left + 1)
            right += 1
        return ans

第八题:替换子串得到平衡字符串

Leetcode1234：替换子串得到平衡字符串：中等题 （详情点击链接见原题）

有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」

第九题:定长子串中元音的最大数目

Leetcode1456:定长子串中元音的最大数目：中等题 （详情点击链接见原题）

给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数

python代码解法:

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = ['a', 'e', 'i', 'o', 'u']
        left, right = 0, 0
        count = 0
        max_count = 0
        while k > 1:
            if s[right] in vowels:
                count += 1
                max_count = max(count, max_count)
            right += 1
            k -= 1
        while right < len(s):
            if s[right] in vowels:
                count += 1
                max_count = max(count, max_count)
            right += 1
            if s[left] in vowels:
                count -= 1
                max_count = max(count, max_count)
            left += 1
        return max_count

第十题:重复的DNA序列

Leetcode187:重复的DNA序列：中等题 （详情点击链接见原题）

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案

解题思路：
从左到右处理字符串 s，使用滑动窗口得到每个以 s[i] 为结尾且长度为 10 的子串，同时使用哈希表记录每个子串的出现次数，如果该子串出现次数超过一次则加入答案
注意：为了防止相同的子串重复添加到答案而又不使用常数较大的 Set结构，可以规定当且仅当该子串在之前出现过一次（加上本次恰好为两次时）将子串加入答案
python代码解法:

from collections import Counter


class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        left, right = 0, 9
        ans = []
        count = Counter()
        while right < len(s):
            if right - left + 1 == 10:
                count[s[left: right + 1]] += 1
            if count[s[left: right + 1]] > 1 and s[left: right + 1] not in ans:
                ans.append(s[left: right + 1])
            left += 1
            right += 1
        return ans

第十一题:爱生气的书店老板

Leetcode1052：爱生气的书店老板：中等题 （详情点击链接见原题）

有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开

python代码解法:

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        ans = 0
        for i in range(0, len(customers)):
            if grumpy[i] == 0:
                ans += customers[i]  # 将原本就满意的客户加入答案
                customers[i] = 0  # 将对应的customers[i]变为0

        # 在customer中找到连续一段长度为minutes的子数组使得其总和最大
        left, right = 0, 0
        max_customers = 0
        total = 0
        while right < len(customers):
            total += customers[right]
            if right - left + 1 >= minutes:
                max_customers = max(max_customers, total)
                total -= customers[left]
                left += 1
            right += 1
        return max_customers + ans

第十二题:水果成篮

Leetcode904:水果成篮：中等题 （详情点击链接见原题）

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类

解题思路：统计最大的连续的数组长度，有树的类型限制连续移动，可以用滑动窗口解决连续数组问题找出最长子数组使最多包含两种水果
python代码解法:

from collections import Counter

from typing import List


class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        temp = Counter()
        left, right = 0, 0
        ans = 0
        while right < len(fruits):
            temp[fruits[right]] += 1   # 1.将右边界的元素添加至滑动窗口中
            while len(temp) > 2:  # 2.当滑动窗口中树的种类大于2,停止扩张右边界,开始收缩左边界
                if temp[fruits[left]] != 0:  # 3.当左指针指向的元素在滑动窗口中
                    temp[fruits[left]] -= 1   # 4.移除窗口中左指针指向的元素
                    if temp[fruits[left]] == 0:  # 5.如果该元素为0,则将该类型的元素pop掉,留着统计下一个种类的元素
                        temp.pop(fruits[left])
                left += 1
            ans = max(ans, right - left + 1)
            right += 1
        return ans

第十三题:删掉一个元素以后全为 1 的最长子数组

Leetcode1493：删掉一个元素以后全为 1 的最长子数组：中等题 （详情点击链接见原题）

给你一个二进制数组 nums ，你需要从中删掉一个元素。
请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。
如果不存在这样的子数组，请返回 0 。

python代码解法:

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        left, right = 0, 0
        zero_count = 0
        ans = 0
        while right < len(nums):
            if nums[right] == 0:
                zero_count += 1
            if zero_count > 1:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1
            if zero_count <= 1:
                ans = max(ans, right - left + 1)
            right += 1
        return ans - 1

第十四题： 乘积小于 K 的子数组

Leetcode713. 乘积小于 K 的子数组：中等题 （详情点击链接见原题）

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目

python代码解法:

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        left, right = 0, 0
        ans = 0
        temp = 1
        while right < len(nums):
            temp *= nums[right]
            while temp >= k:
                temp //= nums[left]
                left += 1
			# 每次右指针移到一个新位置,应该加上x种数组组合
			# nums[right]
			# nums[right - 1], nums[right]
			# nums[left],...nums[right - 1], nums[right]
            ans += (right - left + 1)   
            right += 1
        return ans

第十五题： 最短且字典序最小的美丽子字符串

Leetcode2904. 最短且字典序最小的美丽子字符串：中等题 （详情点击链接见原题）

给你一个二进制字符串 s 和一个正整数 k 。
如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串

python代码解法:

class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        if s.count('1') < k:
            return ''

        ans = s    # 初始化为 s
        left, right = 0, 0
        count = 0
        while right < len(s):
            if s[right] == '1':
                count += 1

            while count > k or s[left] == '0':
                if s[left] == '1':
                    count -= 1
                left += 1
            if count == k:
                temp = s[left: right + 1]
                if len(temp) < len(ans) or (len(temp) == len(ans) and temp < ans):
                    ans = temp
            right += 1
        return ans

二、滑动窗口 + 哈希表

第一题:存在重复元素II

Leetcode219:存在重复元素II：简单题 （详情点击链接见原题）

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

python代码解法:

from collections import Counter

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        left, right = 0, 0
        slide_window = Counter()
        while right < len(nums):
            if nums[right] in slide_window:
                if slide_window[nums[right]] >= 1:
                    return True
            slide_window[nums[right]] += 1
            if right - left >= k:
                slide_window[nums[left]] -= 1
                left += 1
            right += 1
        return False

第二题:无重复字符的最长子串

Leetcode3-无重复字符的最长子串：中等题 （详情点击链接见原题）

1. 当移动 right 扩大窗口即加入字符时,应该更新哪些数据?

初始化Counter(用字典也行)记录滑动窗口中的元素以及元素出现的次数，right向右滑扫描s的过程中将元素和元素出现的次数记录在Counter中

2. 什么条件下窗口应该暂停扩大?

当滑动窗口中出现次数大于 1 的元素(即出现重复字符时)窗口应该停止扩大

3. 当移动left缩小窗口,即移出字符时应该更新哪些数据?

left指向的元素时需要移出滑动窗口的元素，把他在滑动窗口中出现的次数 -1

4. 我们要的结果是在扩大窗口时还是缩小窗口还是窗口暂停扩大的时候进行更新?

在窗口进行扩大的时候进行更新，题目求无重复字符最长子串，故我们在这里对上次记录的结果和新的满足条件的窗口(right - left)取一个最大值

python代码解法:

from collections import Counter


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window = Counter()
        left, right = 0, 0
        res = 0
        while right < len(s):
            window[s[right]] += 1
            while window[s[right]] > 1:
                window[s[left]] -= 1
                left += 1  # 左指针向→滑动
            right += 1	  # 右指针向→滑动
            res = max(res, right - left)
        return res

第三题:字符串的排列

Leetcode567-字符串的排列：中等题 （详情点击链接见原题）

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false

学过排列组合的同学可以知道
如:ABC的排列有 ABC,ACB,BCA,BAC,CAB,CBA 6种结果
题目要求 s2 中是否包含 s1 的排列，所以我们应在 滑动窗口长度即right - left等于 s1 子串的长度时停止扩大进行检查
相较于上题，窗口在停止扩大的时候更新结果，我们比较窗口内的有效字符个数即可断定 s2 中是否包含 s1 中的排列

while right - left == len(s1):
	if valid == len(need):
		return True

解题思路:
由于排列不会改变字符串中每个字符的个数，所以只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的排列
用一个哈希表对滑动窗口中的元素进行计数
1.维护一个窗口大小为 len(s1) 的滑动窗口
2.在滑动窗口往右滑的过程中
3.用 match 存储滑动窗口内的字符和 s1中的字符的匹配数
直接附上该题完整解法的Python代码

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        left, right = 0, 0
        slide_window = {
    }
        count = Counter(s1)
        match = 0
        while right < len(s2):
            slide_window[s2[right]] = slide_window.get(s2[right], 0) + 1
            if s2[right] in count:
                if slide_window[s2[right]] == count[s2[right]]:
                    match += 1
            right += 1
            while right - left >= len(s1):  # 开始移动左指针收缩左窗口
                if match == len(count):
                    return True
                if s2[left] in count:
                    if slide_window[s2[left]] == count[s2[left]]:   # 判断即将移出窗口的元素是否是==s1中的匹配数
                        match -= 1
                slide_window[s2[left]] -= 1
                left += 1
        return match == len(s1)

第四题:找到字符串中所有的字母异位词

Leetcode438-找到字符串中所有的字母异位词：中等题 （详情点击链接见原题）

给定两个字符串 s 和 p,找到 s 中所有 p 的异位词的子串,返回这些子串的起始索引
注: 异位词是指有相同字母重新排列形成的字符串(包括相同的字符串)

字母异位词的本质就是排列，换了一种说法而已
本题相较于上一题字符串的排列改动点如下，我们只需在 s 中找到一个 p 的排列后记录下这个位置索引,跟上题不能说差不多简直就是一模一样，在滑动窗口长度等于p的长度窗口暂停扩大的时候更新结果

result = []
while right - left == len(t):
	if valid == len(need):
		result.append(left)

附上该题完整的Python代码

from collections import Counter


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        slide_window = {
    }
        left, right = 0, 0
        valid = 0
        count = Counter(p)
        result = []  # 保存结果集
        while right < len(s):
            slide_window[s[right]] = slide_window.get(s[right], 0) + 1
            if slide_window[s[right]] == count[s[right]]:
                valid += 1
            right += 1
            while right - left >= len(p):   # 滑动窗口维持 p 字符的长度
                if valid == len(count):     # 如果滑窗中的有效字符等于count的有效长度
                    result.append(left)     # 将起始位置加入结果集
                if slide_window[s[left]] == count[s[left]]:
                    valid -= 1
                slide_window[s[left]] -= 1
                left += 1
        return result

第五题:最小覆盖子串

Leetcode76-最小覆盖子串：困难题 （详情点击链接见原题）

给你一个字符串 s,一个字符串 t,请你在字符串 s 中找出包含 t 所有字母的最小子串，如果 s 中不存在涵盖t所有字符的子串则返回空串
注: 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量

解题思路
由于 t 中可能存在重复字符，所以我们可以借助字典(哈希表)来对t中的字符和字符出现的次数进行计数，这里我们借助于python的内置collections库中的Counter，其实用字典也一样，这里纯属偷懒

from collections import Counter
need = Counter(t)

对子串做好记录以后我们还需对左右指针维护的滑动窗口内的元素和每个元素的出现次数进行统计

window = Counter()	# 初始化空字典用来统计左右指针滑动的过程中滑动窗口内的元素和元素出现的次数

# 双指针
left, right = 0, 0
valid = 0	# 有效匹配字符个数，滑窗内的字符以及该字符出现的次数和==子串中的对应字符valid才+1
start = 0	# 用来记录最小子串的起始覆盖索引
substring_len = float('inf')	# s中包含t中所有字符的最小子串的长度,初始化为无穷大,方便后续更新覆盖

1.当移动 right 扩大窗口即加入字符时,应该更新哪些数据?
右指针向右滑动遍历s串，窗口扩大,window记录窗口内的元素及元素出现的次数
对于即将加入窗口的新元素(即right指针所指的元素)
我们不仅需要判断它是否是子串中的元素，如果是窗口内的对应元素数量＋1，
还要判断滑动窗口中元素的数量和子串中对应元素的数量相等，则有效匹配字符个数valid+=1

while right < len(s):
	if s[right] in list(need.keys()):
	    window[s[right]] += 1	# 窗口内对应元素数量+1
	    if window[s[right]] == need[s[right]]:	# 如果对应元素数量相等则对valid+1
	       valid += 1
	right += 1  # 右指针向→滑动

2.什么条件下窗口应该暂停扩大?
在右指针向右滑的过程中一旦滑动窗口和子串中的元素及元素出现的次数都能匹配上即 valid == len(need)，说明滑动窗口已经包含t子串，此时右指针应该暂停扩大

注:我们要的结果是在扩大窗口时还是缩小窗口还是窗口暂停扩大的时候进行更新?

本题中我们是在窗口暂停扩大的时候判断此时的窗口长度是否小于之前的记录的窗口长度，如果小于则记录下窗口的起始位置和更新s中包含t子串的子串长度

while valid == len(need):
    if right - left < substring_len:
        start = left	# 记录下最小子串的起始覆盖索引
        substring_len = right - left	# 更新s中包含t子串的子串长度

注意上面的黄色字体，上面的代码逻辑发生在右指针向右滑的过程中，所以上面的代码应该嵌套在右指针向右滑动的大循环中

3.当移动left缩小窗口,即移出字符时应该更新哪些数据?
和移动右指针将元素加入到滑动窗口中的操作相同，当我们移动左指针收缩窗口将元素从窗口中移出的时候
我们不仅需要判断它是否是子串中的元素，如果是窗口内的对应元素数量 - 1，
还要判断滑动窗口中该元素的数量和子串中对应该元素的数量相等，如果相等那么移出该元素必定导致有效匹配字符个数-1即valid -= 1

if s[left] in list(need.keys()):
    if window[s[left]] == need[s[left]]:	# 因为移出字符在
        valid -= 1
    window[s[left]] -= 1	# 滑动窗口内对应元素的数量-1
left += 1       # 左指针向→滑动

Python完整代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need, window = Counter(t), Counter()  # need用于记录需要匹配的t串中的字符以及字符出现的频率
        left, right = 0, 0
        valid = 0		# valid用于记录已经匹配成功的有效字符的个数
        start = 0       # 记录最小子串的起始覆盖索引,初始化为0
        substring_len = float('inf')    # 将长度初始化为无穷大
        while right < len(s):
            if s[right] in list(need.keys()):
                window[s[right]] += 1
                if window[s[right]] == need[s[right]]:  # 当对应字符出现的频率相等,对应的 valid + 1
                    valid += 1

            right += 1  # 右指针向→滑动

            # 经过上面的处理之后已经可以将
            while valid == len(need):
                if right - left < substring_len:
                    start = left	# 记录下最小子串的起始覆盖索引
                    substring_len = right - left
                if s[left] in list(need.keys()):
                    if window[s[left]] == need[s[left]]:
                        valid -= 1
                    window[s[left]] -= 1
                left += 1       # 左指针向→滑动
        return s[start:start + substring_len] if substring_len != float('inf') else ""

第六题:删除子数组的最大得分

Leetcode1695. 删除子数组的最大得分：中等题 （详情点击链接见原题）

给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。
返回 只删除一个 子数组可获得的 最大得分

Python完整代码

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        window_sum = 0
        ans = 0
        slide_window = Counter()

        left, right = 0, 0
        while right < len(nums):
            slide_window[nums[right]] += 1
            window_sum += nums[right]

            while slide_window[nums[right]] > 1:
                window_sum -= nums[left]
                slide_window[nums[left]] -= 1
                left += 1
            ans = max(ans, window_sum)
            right += 1
        return ans

第七题:串联所有单词的子串

Leetcode30. 串联所有单词的子串：困难题 （详情点击链接见原题）

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串

Python完整代码

from collections import Counter


class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        word_len = len(words[0])  # 单个单词的长度
        words_map = Counter(words)  # 统计单词和单词出现的频率
        ans = []
        for i in range(len(words[0])):   # 试点
            valid = 0  # valid用来记录有效匹配个数
            left = i
            right = i
            hash_map = Counter()
            while right < len(s):
                if s[right:right + word_len] in words_map:
                    hash_map[s[right:right + word_len]] += 1
                    if hash_map[s[right:right + word_len]] == words_map[s[right:right + word_len]]:
                        valid += 1
                right += word_len  # 从下个单词的起始位置开始匹配
                if right - left == len(words) * len(words[0]):
                    if valid == len(words_map):
                        ans.append(left)
                    if s[left:left + word_len] in words_map:
                        if hash_map[s[left:left + word_len]] == words_map[s[left:left + word_len]]:
                            valid -= 1
                        hash_map[s[left:left + word_len]] -= 1
                    left += word_len
        return ans

三、变长滑动窗口

第一题:统计完全子数组的数目

Leetcode2799. 统计完全子数组的数目：中等题 （详情点击链接见原题）

给你一个由 正 整数组成的数组 nums 。如果数组中的某个子数组满足下述条件，则称之为 完全子数组

解题思路
用 distinct 表示整个数组不同元素的数目，使用哈希表记录滑动窗口中每个元素的出现次数，对每个右端点执行如下操作

1. 在哈希表中将 nums[right] 的出现次数 +1

2. 当哈希表中的元素个数等于 distinct 时执行如下操作

   • 将 nums[left] 的出现次数 -1，如果 nums[left] 的次数变为 0，将 nums[left] 从哈希表中移除，将 left 右移一位

3. 以 right 作为结束下标的完全子数组的数目是 left，将完全子数组的数目增加 left

   • 如果 left > 0，则以 right 作为结束下标的最短完全子数组的开始下标是 left - 1，因此结束下标是 right 且开始下标在范围 [0, left - 1] 中的子数组都是完全子数组，以 right 作为结束下标的完全子数组的数目是 left
   • 如果 left= 0，则不存在以 right 作为结束下标的完全子数组

Python完整代码

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        n = len(set(nums))
        count = Counter()
        ans = 0
        right, left = 0, 0
        while right < len(nums):
            count[nums[right]] += 1
            while len(count) == n:
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    count.pop(nums[left])
                left += 1
            ans += left
            right += 1
        return ans

四、滑窗+双端队列

第一题:绝对差不超过限制的最长连续子数组

Leetcode1438. 绝对差不超过限制的最长连续子数组：中等题 （详情点击链接见原题）

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit

解题思路
要求窗口的最大长度，我们必须时刻知道当前窗口内的最值，才能判断是否满足限制
此题的难点在于当一个元素入窗或者出窗时，如何以最小的时间开销找到新的窗口内的最大值和最小值
很容易想到用堆来记录最值，但是插入删除操作是 O(logn) 级别，还有没有更好的解决方案呢？
双端队列：插入删除头尾元素都是O(1)
min_q: (从队头—>队尾)从小到大存储窗口中的元素
max_q: (从队头—>队尾)从大到小存储窗口中的元素

Python完整代码

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        right, left = 0, 0
        min_q = deque()
        max_q = deque()
        ans = 0
        while right < len(nums):
            while min_q and nums[right] < min_q[-1]:
                min_q.pop()
            while max_q and nums[right] > max_q[-1]:
                max_q.pop()
            min_q.append(nums[right])
            max_q.append(nums[right])
            while max_q[0] - min_q[0] > limit:
                if min_q[0] == nums[left]:
                    min_q.popleft()
                if max_q[0] == nums[left]:
                    max_q.popleft()
                left += 1
            ans = max(ans, right - left + 1)
            right += 1
        return ans

总结

在我们对滑动窗口进行了由浅入深、由难到易的介绍后，博主在最后为大家介绍一些高频面试练手题，算法题没有固定模板，对于可以总结框架的题型我们对它进行分析打磨，节省大家在刷题准备面试过程中的时间成本，提高大家的效率