什么是滑动窗口
滑动窗口是算法题当中一种常见的解题方法，属于双指针的一种，常用于数据结构为数组（列表）、字符串类型的题目。其目的在于通过维护两个指针left、right，并将left和right当作题目给出数组（列表）、字符串中的一个子数组（列表）、字符串的左右端点，通过不断增大两指针的值，使得由两指针维护的窗口始终满足题目所给要求，最后计算答案。
如上图所示，在算法刚开始执行时窗口会先不断扩大，此时可以确保由left指向的a0作为左端点和right指向的a3作为右端点所构成的窗口是符合题意的。假设当窗口继续扩大，即right继续右移指向a4时，窗口不再满足题目要求，这个时候就需要通过右移left指向新的元素使得窗口缩小，以重新满足题目要求。假设当left指向a2时，由两指针构成的窗口可重新满足题意，如下图所示：
这样由a2到a4构成的新的窗口又重新满足了题意。最后只需根据题目要求，计算答案的个数即可。由于移动两个指针的过程就像是一个窗口在移动，故得名为滑动窗口。而定长滑动窗口则又是滑动窗口的一个特殊形式，它的窗口大小是固定的，也就是窗口的左右端点需要一起移动，在后文中会对定长滑动窗口进行举例介绍。双指针、滑动窗口、定长滑动窗口的关系如下图所示：
双指针是最基础的方法，滑动窗口是双指针的应用，定长滑动窗口是一种特殊的滑动窗口。
滑动窗口的使用场景
当一道题目能用 滑动窗口解决 时，它一般符合以下三个特征：
- 题目背景的数据结构为数组（列表）、字符串
- 题目需要求 “满足条件的子数组（列表）、子字符串个数”，或 “满足条件的子数组（列表）、子字符串的最大长度或个数”
- 滑动窗口适用的题目往往具有 单调性
对第三点做进一步说明：当窗口扩张时，窗口整体与题目条件的关系会呈现出一定的单调性：要么越容易满足条件（例如要求子数组和大于某个值 k，且数组元素为非负数时），要么越不容易满足条件。一旦窗口失去题意，就可以通过移动左指针缩小窗口来重新满足条件。这种单调性是滑动窗口能够高效发挥作用的关键。
当一道题目能使用更特别的 定长滑动窗口 时，除了符合上述的第一点，还应当满足以下特征：
- 题目明确说明需要找一个大小为k的子数组（列表）、字符串，使其满足题目条件
- 题目要求在固定大小的窗口上进行统计或优化，例如 “统计该窗口内某类元素的个数”，或 “计算和、最大值、平均值等”
相比一般滑动窗口，由于定长滑动窗口固定了窗口大小，寻找子数组的过程中无论结果如何左右指针都会一起移动，本身就不会回溯，故定长滑动窗口的使用对单调性并无要求，但其使用场景更为局限，判断条件更直观明确。
普通滑动窗口能否使用的核心，仍然在于题目是否具有单调性。以找到元素和大于k的子数组为例：通过第一小节什么是滑动窗口我们知道，当窗口不满足条件时，右指针会右移使得窗口逐渐满足条件。对于上图中具有单调性的数组，随着指针不断右移，子数组将越来越符合条件，因为它每次都是增加一个正数，使得子数组和越来越接近k。而不含单调性的数组随着指针右移，它有时因为加了一个正数，使得子数组和离k越接近，但有时候又因为加了一个负数使得子数组和离k越遥远，这就是不含有单调性的具体体现。
关于单调性的必需的原因，将在下一节中介绍。
一般滑动窗口的原理
注:本小节若无特别说明，提到的滑动窗口指的均是一般滑动窗口，而非定长滑动窗口
在介绍单调性对于使用一般滑动窗口的必要性之前，首先介绍滑动窗口的本质。
滑动窗口的本质实际上是对暴力解法的一种剪枝，也就是利用滑动窗口省去很大一部分不必要的判断。当我们需要找到一个数组的子数组，使其满足某种条件并统计个数或者返回需要满足的条件的值时，暴力解法是遍历这个数组当中的所有子数组，分别判断是否符合题意并记录结果，具体的解题伪代码如下:
class Solution:
def Brute_Force(self,nums:list[int]) -> int:
"""
暴力法
nums为待遍历数组
"""
ans = 0 #用来记录答案
for i in range(len(nums)):
for j in range(i,len(nums)):
if nums[i:j + 1] meets the condition:
ans += 1
return ans不难判断暴力解法的时间复杂度为O（n²）。
当题目给出的数组nums具有单调性时，也就是要么子数组越长越容易满足条件要么子数组越短越容易满足条件，就可以省去很多不必要的判断，使得左右指针只用向一个方向移动，无需回溯。下文分别称这两种情况为越长越合法和越短越合法。当给出数组nums具有单调性时，一般会有以下两条性质:
- 若由left 和 right构成的窗口不符合题意，那么由left 和 right + 1、right + 2、right + 3….len（nums） - 1 构成的窗口依然不符合题意
- 若由left 和 right构成的窗口符合题意,那么由left + 1、left + 2…..right 和 right 构成的窗口依然符合题意
注:上述两条性质适用于单调性为越短越合法的题目，对于单调性为越长越合法的题目，需将第一条性质中的两个不符合改为符合，将第二条性质中的符合改为不符合。*
对于单调性为越短越合法的题目而言，子数组越大，该子数组就越不满足题目要求，如下图所示：
假设由left,right两指针构成的窗口恰好此时不满足条件了，由于单调性为越短越合法，也就是当窗口越大时，反而越不满足条件，那么由left和right之后的元素构成的窗口自然也是不满足条件的，之后就不用再进行判断了，这即为上述性质一。
如上图，假设由left和right构成的窗口此时是满足条件的，由于数组越短越合法，则从left到right之间的所有元素和right构成的窗口都是满足条件的，在后续又可以省去这一部分的判断，这即为上述性质二。
正如前文所说，滑动窗口类型的题目，left和right两个指针只会向同一个地方移动，绝不回溯，这正是因为题目具有单调性，两个指针的作用分别如下:
- 右指针:负责扩大窗口使窗口不断满足题意，但在扩大窗口的过程中可能会由于新加入窗口的元素过大等原因，使得窗口不再满足题意
- 左指针:负责缩小窗口使窗口重新满足题意
过程中左指针无需回溯可以理解成: 随着右指针的移动，窗口越来越大，直至不满足条件，左指针通过右移使其重新满足条件。如果左指针回溯到开始的位置重新遍历形成了一个大窗口，那么那段不符合题意的小窗口也依然包含在了这个大窗口中，由于越短越合法，故此时这个大窗口一定是不合法的，无需再进行判断。也就是说，性质一确保了左指针无需再回溯，只用从当前位置开始继续遍历。
过程中右指针无需回溯可以理解成: 当左指针发生了移动，说明此时右指针恰好停留在使得窗口不满足条件的位置，也就是当前右指针所指向位置的前一个元素，和先前的左指针以及两指针中间的元素所构成的窗口均合法，故右指针无需再回溯来判断它与当前左指针构成的新窗口是否依然合法，这是由上述性质二确保的。
越长越合法类型的滑动窗口同理。
滑动窗口的解题模板大致如下：
class Solution:
def sliding_windows(self,nums:list) -> int:
"""
滑动窗口
"""
left = ans = 0
for right,i in enumerate(nums):
#根据题目条件
#计算需要的值
while ans not meets the condition:
#用计算出来的值
#减去左指针指向的值
left += 1 #左指针右移
ans += right - left + 1 #越短越合法类型
ans += left #越长越合法类型
return ans由于外层循环是right不断右移直至数组的末尾，内层循环是left不断右移（不回溯）直至数组的末尾，每个数组元素最多被操作两次（一次进窗口、一次出窗口）。故时间复杂度为O（2n），省略常数项，滑动窗口的时间复杂度可以达到O（n）。
最后介绍单调性的必要性。倘若此时题目给出的数组不具有单调性，即有正有负。以找和小于k的子数组为例，假设在一个负数元素之前的所有元素均为正数，那么当该元素进入窗口时，它缩小了子数组的和，这就使得和小于k的子数组可能会出现在以当前left左边的元素为左端点的窗口中，如下图所示：
当-5进入窗口并作为窗口的右端点时，通过上文的分析我们知道，若具有单调性，由于性质一，left不必回溯。但对于这种不具有单调性的情况，当-5进入窗口时，left指向下标为0的元素1，此时新窗口依然符合题意，也就是左指针此时需要回溯，并未达到节省时间复杂度的目的，不符合滑动窗口的逻辑，故不能使用滑动窗口，这也解释了为什么单调性是使用滑动窗口的必要条件。
定长滑动窗口
定长滑动窗口是一种特殊的滑动窗口，常用在给定一个数组（列表）、字符串，寻找一个大小为k的子数组(列表)、字符串，使其满足“窗口和最大”、“窗口平均值最大”、“窗口内某元素数量最多”等条件。
以数组nums为例，由于nums中长度为k的子数组个数固定为len（nums） - k + 1，定长滑动窗口无论当前窗口结果如何，左右指针都要进行一次的移动来找到下一个窗口，也就是说，对于一个新的窗口而言，它与前一个窗口的区别在于首尾两个元素，如下图所示:
从窗口1变换为窗口2，left指针指向的元素出窗口，right’指针指向的元素进入窗口，也就是只要将统计值减去left指针指向元素带来的影响，再加上right’指针指向元素带来的影响，得到的就是新的窗口的统计值，再利用新窗口的统计值和当前最优统计值进行对比，找到最满足题意的统计值，记录并返回即可。
定长滑动窗口的三步曲如下:
- 构建一个大小为k的窗口
- 记录当前窗口的统计值（如:窗口元素和、窗口元素平均值、窗口内某元素的个数）
- 统计值减去左指针指向值带来的影响，左指针右移、统计值加上右指针指向值带来的影响，右指针右移
又由于窗口大小固定为k，故left指针指向的元素和right指针指向的元素有如下关系: \[ left = right - k + 1 \] 因为right为大小为k的窗口的右端点，除去right指向元素以外，还需往前数k-1 个元素才到left指向元素，故实际上: \[ left = right - (k - 1) = right - k + 1 \] 所以在实际的解题过程中，无需再定义一个左指针left，可直接用上述公式得到left所指向元素。
重复以上第二和第三步，直到统计完所有结果为止。
定长滑动窗口解题的伪代码如下:
class Solution:
def fixed_size_sliding_windows(self,nums:list,k:int) -> int:
"""
定长滑动窗口
k为窗口大小
nums为待进行寻找答案的列表
"""
if k == 0: return alllist
ans = res = 0
for right in range(len(nums)):
#1.构建窗口
res += nums[right]
if right < k - 1:
continue
#2.记录窗口统计值，并与当前最优解比较
ans = max(ans,res)
#3.统计值减去最左边元素带来的影响
res -= nums[right - k + 1]
return ans滑动窗口例题
定长滑动窗口
定长滑动窗口的题目类型一般分为以下两种:
- 找到大小为k的子数组，使其具有最大、最小的元素和等
- 找到大小为k的子数组，使子数组内某元素的个数最小或最大
不管题目描述如何改变，最后都可以转化为上述两种类型。
下文举例介绍定长滑动窗口
1.定长子串中元音的最大数
题目链接：1456.定长子串中元音的最大数
题目描述:
给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为（a, e, i, o, u）。输入输出示例
示例 1：
输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。
示例 2：
输入：s = "aeiou", k = 2
输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母。
示例 3：
输入：s = "leetcode", k = 3
输出：2
解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。
示例 4：
输入：s = "rhythms", k = 4
输出：0
解释：字符串 s 中不含任何元音字母。
示例 5：
输入：s = "tryhard", k = 4
输出：1题目规模:
1 <= s.length <= 10^5
s 由小写英文字母组成
1 <= k <= s.length解题思路:
这道题属于典型的定长滑动窗口类型二，给定一个大小为k的窗口，找到包含元音数量最多的那个窗口并返回结果。
只需按照三部曲：
1.构建第一个窗口并在该过程中统计元音个数
2.将当前窗口的元音个数和当前最优解比较
3.判断left指向的元素和right + 1指向的元素是否为元音字母，并作出相应操作
具体代码如下。解题代码:
class Solution:
def maxVowels(self, s: str, k: int) -> int:
"""
定长滑动窗口
"""
vowels = 'aeiou' #记录元音字母
ans = res = 0 #ans是返回值，res是临时变量
for right in range(len(s)):
#1.统计第一个窗口元音个数
if s[right] in vowels:
res += 1
if right < k - 1:
continue
#2.和当前最优解比较
ans = max(res,ans)
#3.判断左指针指向元素的性质，并移动左指针
if s[right - k + 1] in vowels:
res -= 1
return ans复杂度分析:
- 时间复杂度:O（n）
- 空间复杂度:O（1）
2.可获得的最大点数
题目链接:1423. 可获得的最大点数
题目描述：
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。输入输出示例；
示例 1：
输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
示例 2：
输入：cardPoints = [2,2,2], k = 2
输出：4
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。
示例 3：
输入：cardPoints = [9,7,7,9,7,7,9], k = 7
输出：55
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。
示例 4：
输入：cardPoints = [1,1000,1], k = 1
输出：1
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。
示例 5：
输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出：202题目规模：
1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length解题思路:
这道题则对应定长滑动窗口题目的类型一，只不过需要用到逆向思维。
由于抽牌只能从cardPoints的左右两边抽，并且只能抽k张，也就是最后牌组里会剩下len(cardPoints) - k张牌，且这k张牌是连续的。
那么题目就变成了：
从cardPoints中找到一个大小为len(cardPoints) - k的子数组，使得这个子数组的元素和最小。
具体代码如下。解题代码:
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
"""
定长滑动窗口
窗口为0的话需要特判
"""
l = len(cardPoints) - k #逆向思维的窗口大小
if l == 0: return sum(cardPoints)
ans,res =sum(cardPoints) + 1,0 #ans记录答案，res记录中间值
for right in range(len(cardPoints)):
#1.构建窗口并记录值
res += cardPoints[right]
if right < l - 1:
continue
#2.与当前最优解比较
ans = min(ans,res)
#3.移除左指针指向元素
res -= cardPoints[right - l + 1]
return sum(cardPoints) - ans当窗口大小为0时需要特判。因为res减去的是窗口最左边的元素，如果一个窗口大小为0的话，那它将不存在所谓最左边的元素，代入进倒数第二行，当right = len(cardPoints) - 1时将会越界。
复杂度分析:
时间复杂度:O（n）
空间复杂度:O（1）
不定长滑动窗口
不定长滑动窗口对题目有着严格的单调性要求，一般分为以下几种类型：
- 越短越合法求最长的子数组
- 越长越合法求最短的子数组
- 求子数组的个数
其中求子数组的个数又可以分为：
- 求某值大于k的子数组个数
- 求某值小于k的子数组个数
- 求某值恰好等于k的子数组个数
对于不定长滑动窗口，不管题目描述如何改变，大部分都能够转换为以上几种类型
下文举例介绍不定长滑动窗口
1.无重复字符的最长子串
题目链接:3. 无重复字符的最长子串
题目描述:
给定一个字符串 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 由英文字母、数字、符号和空格组成解题思路：
这是一道很经典的具有单调性的题目。子字符串越长，子字符串含有的字符就越多，含有重复字符的概率就越大，越不符合题意。可以判断这是一道越短越合法类型的题目，故可以采用滑动窗口。
利用"滑动窗口的原理"小节中介绍的滑动窗口的两条性质，可以有效剪枝。
具体代码如下。
left不用回溯:越短越合法，回溯的话相当于依然包含了不合法子字符串
right不用回溯:由于当right移动到不符合题意的位置时，left会移动使其重新符合题意。也就是在统计时，当前的窗口正是以当前right为右指针所构成的最大的能满足题意的窗口解题代码
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
"""
不定长滑动窗口
越短越合法，求个数
"""
left = ans = 0
#定义一个字典c来记录每个答案的个数
c = defaultdict(int)
for right,i in enumerate(s):
c[i] += 1
#如果不符合题意了，就移动左指针让其重新符合题意
while c[i] > 1:
c[s[left]] -= 1
left += 1
#每一次符合题意的子字符串长度都是right - left + 1
ans = max(ans,right - left + 1)
return ans复杂度分析:
时间复杂度:O（n）
空间复杂度:O（1）字符集大小为128，c的最大长度即为128，省略常数项，即为O（1）
2.将x减到0的最小操作数
题目链接:1658.将x减到0的最小操作数
题目描述:
给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1输入输出示例:
示例 1：
输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
示例 2：
输入：nums = [5,6,7,8,9], x = 4
输出：-1
示例 3：
输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。题目规模:
1 <= nums.length <= 105
1 <= nums[i] <= 104
1 <= x <= 109解题思路:
同定长滑动窗口例题2一样，这道题目依然可以利用逆向思维，将题目改写成:
找到最大连续的子数组k，使其和为sum(nums) - x，如果存在,返回len(sums) - len(k)，否则返回-1
判断题目的单调性。由于数组元素均为正数，当子数组越长，子数组和就越大，越不符合题意，故可以使用滑动窗口解决。
但此时还应注意一种情况，由于此题采用的是逆向思维，按照前文，若当前窗口不符合题意，则需要移动左指针使其重新符合题意
记要求的和为 i = sum(nums) - x，当前子数组和为j，则当j > i时需要重新移动left
但如果i＜0，即数组所有元素加起来的和也小于x，由于数组元素均为正数，无论怎么移动left指针，j > i一定成立，此时会进入死循环。
故需要特判这种情况，直接返回-1.
具体代码如下。解题代码:
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
"""
逆向思维
不定长滑动窗口
子数组越短越合法
"""
#特判所有元素不够加的情况
if sum(nums) < x: return - 1
ans = -1
#i为窗口要找的值
i = sum(nums) - x
left = res = 0
for right,j in enumerate(nums):
res += j
while res > i:
res -= nums[left]
left += 1
#符合条件才记录答案
if res == i:
ans = max(ans,right -left + 1)
#如果题目当中没有符合题意的子数组，ans = -1，直接返回-1，否则返回除去ans外剩下的元素长度
return len(nums) - ans if ans != -1 else - 1复杂度分析:
时间复杂度：O（n)
空间复杂度：O（1）
3.最小覆盖字串
题目链接：76. 最小覆盖子串
题目描述:
给你一个字符串 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 由英文字母组成解题思路：
首先明白覆盖的含义。当S的子字符串中的对应字符个数大于等于t中对应的字符个数，此时就说子字符串覆盖了t。
再来看单调性，当S的子字符串越长，里面的字符就越多，就越有可能包括所有t中出现的字符串，故这是一道越长越合法类型的题目。
在此基础上求最短的符合条件的子字符串。
同理，先让窗口逐渐扩大，直到其符合条件。当其符合条件时，当前right指针指向的元素之后的所有元素与当前left指针指向元素所构成的窗口均符合题意，但长度不是最小，故由性质一进行剪枝，无需再判断。
而Counter()可以很方便的的判断字符串中的字符个数并进行比较。
具体代码如下。解题代码:
class Solution:
def minWindow(self, s: str, t: str) -> str:
"""
越长越合法求最短
"""
c = Counter()
d = Counter(t)
left,cnt,ans = 0,len(s) + 1,""
for right,i in enumerate(s):
c[i] += 1
#此时覆盖了t字符串
while c >= d:
if right - left + 1 < cnt:
ans = s[left:right + 1]
cnt = right - left + 1
c[s[left]] -= 1
left += 1
return ans复杂度分析:
时间复杂度:O（|Σ|·|s| + |t|）
while c >= d的条件在每次right移动时会判断一次（≤|s| 次），并且每次left移动也会导致一次判断（left全程最多移动 ≤|s| 次），所以条件判断总次数 ≤ 2|s|，每次判断代价为O(|Σ|)，再加上构造Counter(t)的O(|t|)。当 |Σ| 为常数（如本题 52 个字母）时，复杂度可简化为O(|s| + |t|)。空间复杂度:O（1） 由于s和t均由英文字母构成，c和d大小最多为52，和为104，故空间复杂度为常数。
4.不间断子数组
题目链接:2762. 不间断子数组
题目描述：
给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是 不间断 的：
i，i + 1 ，...，j 表示子数组中的下标。对于所有满足 i <= i1, i2 <= j 的下标对，都有 0 <= |nums[i1] - nums[i2]| <= 2 。
请你返回 不间断 子数组的总数目。
子数组是一个数组中一段连续 非空 的元素序列。输入输出示例:
示例 1：
输入：nums = [5,4,2,4]
输出：8
解释：
大小为 1 的不间断子数组：[5], [4], [2], [4] 。
大小为 2 的不间断子数组：[5,4], [4,2], [2,4] 。
大小为 3 的不间断子数组：[4,2,4] 。
没有大小为 4 的不间断子数组。
不间断子数组的总数目为 4 + 3 + 1 = 8 。
除了这些以外，没有别的不间断子数组。
示例 2：
输入：nums = [1,2,3]
输出：6
解释：
大小为 1 的不间断子数组：[1], [2], [3] 。
大小为 2 的不间断子数组：[1,2], [2,3] 。
大小为 3 的不间断子数组：[1,2,3] 。
不间断子数组的总数目为 3 + 2 + 1 = 6 。题目规模:
1 <= nums.length <= 105
1 <= nums[i] <= 109解题思路:
首先判断题目意思，找到一个子数组，使其中任意两个元素的差的绝对值均小于等于2。
这等价于，找到一个子数组，使得该子数组中最大的元素和最小的元素差值小于等于2。
再来判断题目的单调性，当子数组内元素越多，子数组中最大和最小的元素差就可能越大，就越不合法。
故这是一个越短越合法类型的题目。
题目要求统计合法的子数组个数，只需要每次统计时加上right - left + 1即可。
具体代码如下。解题代码:
class Solution:
def continuousSubarrays(self, nums: List[int]) -> int:
"""
越短越合法
求数组个数
"""
left = ans = 0
c = defaultdict(int) #记录当前窗口的元素
for right,i in enumerate(nums):
c[i] += 1
#如果不符合题意，就让它变成符合题意为止
while max(c) - min(c) > 2:
c[nums[left]] -= 1
if c[nums[left]] == 0:
del c[nums[left]]
left += 1
ans += right - left + 1
return ans复杂度分析:
时间复杂度:O（n）
将题目要求的差值设为M，即： \[ 0 <= nums[i] - nums[j] <= M(0 <= i <= j <= len(nums) - 1) \] 则时间复杂度为O（（M+1）n），其中n为数组的长度，原因如下：
每一次left指针的移动都伴随着 \[ max(c) - min(c) \] 而字典调用这两个方法的逻辑是遍历整个字典，寻找最大的键。由于题目要求子数组内差值两两之间不能超过M，故最多有M + 1个元素会被存入字典中，max和min两个方法遍历的最坏情况也就是遍历M + 1个元素。而left最多移动n次，故时间复杂度是O（（M+1）n）。
而对于本题，M＝2，代入并省略常数项可得时间复杂度为O（n）。
空间复杂度:O（1）
空间复杂度即为定义的c的最大长度，理由同上。
故空间复杂度最大为O（M + 1）。对于本题，M＝2，代入并省略常数项可得空间复杂度为O（1）。
Q&A：
Q:为什么子数组中最大的元素和最小的元素差值小于等于2即可满足条件?
A:可以看成一根数轴，子数组的最大和最小元素分别对应数轴两端，其余元素全在该数轴内，差的绝对值自然小于等于2.
Q:为什么统计时加上right - left + 1即可？
A:经过分析可知，该题目为越短越合法类型。由性质二可得，对于一个由left,right构成的窗口，如果它满足题意，那么从left到right之间（包含left和right）的所有元素和right构成的窗口均符合题意，这里一共有right - left + 1个元素，即有right - left + 1个合法子数组。而在统计时，对于每一个right，均能确保left在恰好使得窗口满足题意的位置，故直接加上right - left + 1即可。
5.统计好子数组的数目
题目链接:2537. 统计好子数组的数目
题目描述:
给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。
一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。
子数组 是原数组中一段连续 非空 的元素序列。输入输出示例:
示例 1：
输入：nums = [1,1,1,1,1], k = 10
输出：1
解释：唯一的好子数组是这个数组本身。
示例 2：
输入：nums = [3,1,4,3,2,2,4], k = 2
输出：4
解释：总共有 4 个不同的好子数组：
- [3,1,4,3,2,2] 有 2 对。
- [3,1,4,3,2,2,4] 有 3 对。
- [1,4,3,2,2,4] 有 2 对。
- [4,3,2,2,4] 有 2 对。题目规模:
1 <= nums.length <= 105
1 <= nums[i], k <= 109解题思路:
首先分析题目意思，有k对元素相同，那就为一个好子数组，求子数组个数。
即，找到子数组使其相同元素下标对数大于等于k，这是一个越长越合法求个数的问题。
当子数组越大，子数组内元素就越多，相同元素出现的概率就越大，越可能满足题意。
符合单调性，可以使用滑动窗口。
对于每一个加入进窗口的元素，假设窗口内有k个该元素，那么相同元素对数结果需要加k。
而在每次统计时，答案加left 即为”以当前right指针指向元素“作为数组右端点的满足题意的子数组个数。
具体代码如下。解题代码:
class Solution:
def countGood(self, nums: List[int], k: int) -> int:
"""
越长越合法
求合法子数组个数
"""
c = defaultdict(int) #记录窗口内的元素个数
left = ans = cnt = 0 #cnt统计相同元素
for right,i in enumerate(nums):
c[i] += 1
cnt += c[i] - 1 #与当前元素加入窗口之前的相同元素成对
while cnt >= k:
cnt -= c[nums[left]] - 1
c[nums[left]] -= 1
left += 1
ans += left
return ans复杂度分析:
- 时间复杂度:O（n）
- 空间复杂度:O（n）
Q&A:
Q:为什么对于每一个加入进窗口的元素，假设窗口内有k个该元素，那么相同元素对数结果需要加k？
A：当一个新元素进入窗口，此时窗口内每一个和它相同的元素均能和它组成一对，而窗口中一个有k个这样的元素，故结果加k即可。
Q：为什么在每次统计时，答案加left 即为”以当前right指针指向元素“作为子数组右端点的满足题意的子数组个数。
A：经过分析可知，题目为越长越合法求子数组个数的类型。每一次遍历实际上是在找以当前的right指针作为窗口的右端点，会有多少个符合题意的子数组。接下来分两种情况：
当right不断增加，但合法的窗口还没构成时: 此时left不会发生任何移动，依然是初始值0，也就是加上left也不会对结果有任何影响。
当合法的窗口已经构成时，需要移动left使其不合法:
对于right来说，由于经历了while循环使得这个窗口恰好重新不合法，也就是在此时left指针指向元素之前的所有元素，与当前的right指针指向的元素构成的子数组都是合法的，一共有left个元素(下标为left代表前面有left个元素)。
注：多理解：
- 越长越合法
- left指针指向的元素是恰好让窗口不合法的端点元素
6.K个不同整数的子数组
题目链接:992.K 个不同整数的子数组
题目描述:
给定一个正整数数组 nums和一个整数 k，返回 nums 中 「好子数组」 的数目。
如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。
例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。
子数组 是数组的 连续 部分。输入输出示例:
示例 1：
输入：nums = [1,2,1,2,3], k = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
示例 2：
输入：nums = [1,2,1,3,4], k = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
- [4,3,2,2,4] 有 2 对。题目规模:
1 <= nums.length <= 2 * 104
1 <= nums[i], k <= nums.length解题思路:
对于这种要找一个子数组，使其恰好满足某种条件的问题，可以将其转换为：
1.两个越长越合法类型的差
2.两个越短越合法的类型的差
要找不同整数个数恰好为k个的子数组，可以先找”不同整数个数大于k”和“不同整数个数大于等于k”的子数组个数
再用两者做差，即可得到不同整数个数等于k的子数组个数。
要找到这样的子数组，自然是越长越合法，故这是转换为第一种情况。
或者也可以找“不同整数个数小于等于k”和“不同整数个数小于k”的子数组个数。
依然是两个答案做差得到答案。
而要找到这样的子数组，则变成了越短越合法，故这是转换为第二种情况。
而大于k等价于大于等于k+1，小于k等价于小于等于k-1.
故只需要写一个方法，传递不同的参数即可得到需要的答案。
具体代码如下。解题代码:
class Solution:
def subarraysWithKDistinct_atleast(self, nums: List[int], k: int) -> int:
"""
转换为越长越合法
"""
def atleast(j:int) -> int:
ans = left = 0
c = defaultdict(int) #记录当前窗口内的元素
for right,i in enumerate(nums):
c[i] += 1
#当字典长度大于等于j，说明此时字典内不同元素个数足够，窗口合法
while len(c) >= j:
c[nums[left]] -= 1
if c[nums[left]] == 0:
del c[nums[left]]
left += 1
#越长越合法每次直接加left
ans += left
return ans
return atleast(k) - atleast(k + 1)
def subarraysWithKDistinct_atmost(self, nums: List[int], k: int) -> int:
"""
转换为越短越合法
"""
def atmost(j:int) -> int:
ans = left = 0
c = defaultdict(int) #记录当前窗口内的元素
for right,i in enumerate(nums):
c[i] += 1
#当字典长度大于j，说明此时字典内不同元素个数超过了k，窗口不合法
while len(c) > j:
c[nums[left]] -= 1
if c[nums[left]] == 0:
del c[nums[left]]
left += 1
#越短越合法每次统计整个[left,right]区间内的所有子数组
ans += right - left + 1
return ans
return atmost(k) - atmost(k - 1)复杂度分析:
- 时间复杂度:O（n）两次atleast或atmost的时间复杂度均为O（n），故总体时间复杂度也为O（n）
- 空间复杂度:O（k）字典的长度不会超过题目所给出的长度，故空间复杂度为O（k），k为题目要求的数组中恰好有的值的个数。
Q&A:
Q:为什么这类题不能像之前的滑动窗口一样，先构建一个合法窗口，再通过移动左指针缩小窗口，每次找到合法的子数组就将答案加一呢?
A:因为不能确保单调性！！！此类题目没有办法确保当子数组增大，它会越来越符合题意或是越来越不符合题意。以此题为例，假设有这样一个输入： \[ nums = [1,1,1,2,3,1,1],k = 3 \] 若按照前面题目的套路，当left＝0，right=4时符合条件，此时ans+1，再右移left，直到left=3指向2不符合条件时，继续移动right使其重新满足条件。此时right=5，指向列表中的第四个1，又重新符合题意。但是这个right和当前left左边所有元素构成的窗口也依然符合题意。故这种方法不成立。
总结
能否使用定长滑动窗口解题往往在题干中有比较明显的暗示。而在一道题目能否使用普通滑动窗口，最关键的部分就在于判断题目是否具有单调性。充分利用具有单调性的题目的两条性质（此处以越长越合法举例）:
- 若left….right符合题意，那么left…..right + 1、right + 2…len(nums)依然符合题意
- 若left….right不符合题意，那么left、left + 1、left + 2…right…right也依然不符合题意
明确滑动窗口每一次移动right指针实际上是寻找以当前right指针指向的元素作为子数组的右端点，所有符合条件的子数组的过程。
对于越短越合法求最长的类型，当计算答案时，由于中间符合条件的子数组反而更短，故无需考虑
对于越长越合法求最短的类型，当计算答案时，由于中间符合条件的子数组反而更长，故无需考虑
对于求个数类型的滑动窗口，当计算答案时，分别用: \[ ans += right - left + 1 \] 和: \[ ans += left \] 加上所有合法结果即可。
以上为这篇博客的所有内容，欢迎各位友好交流，如有不对之处请批评指正，希望能对你有所帮助！
