专栏简介
上一个专栏，《竞赛算法速成日记》是我为了应对大一下所到来的蓝桥杯国赛和CSP认证所临时准备所学习的算法思想，只能说是提高了广度，并没有学到精髓，在竞赛中发挥的作用并不大（蓝桥杯PyB组喜提国三，CSP认证喜提前60%）。所以，我认为确实有必要系统的，多投入一些时间去学习算法的一整套体系，来应对后面更重要的工作面试。
总体学习路线，我是参照灵茶山艾府大神的这篇文章：分享｜如何科学刷题？
我从文章中扒了一张图，大体就是这样：
算法的知识面是非常广的，我也不奢求完美完成每一个模块，力求在1年内把所有基础的题目都做完，并且每做完一个板块，就来这里更新我自认为这一块知识点的精髓内容(如果我半个月没有更新，欢迎催更~)。当然这最主要的是为了加深我自己的理解，如果能顺带帮到你，那就更好了。
所以，总结一下，这个专栏，《算法笔记》，就是我为了总结消化我所学习到的算法知识，顺带还能帮助到你一点的一个专栏。下面开始正文内容。
PS:由于算法笔记的内容比较多，所以我打算每个大模块都发一篇文章，各自之间分开，不然一篇文章肯定装不下。
1.定长滑动窗口
最初的样子
滑动窗口这个算法，算是我第一次打开leetcode刷题时就有接触到的算法了，当时也是把我狠狠震撼到了。
我之前学习到的滑动窗口是这样的：给定一个字符串和一个子串，求该子串在该字符串中出现的次数(重叠也算)，如果不存在请输出-1。
当时反正是拿双指针折腾了半天，结果最后还超时了，整了个O(n^2)的复杂度。其实正确的做法是，只需要一个指针，然后不断的按照该子串的长度，在字符串中从前到后切片，不断对比这个切片和给定子串，如果相等，则次数加一。这就像我在字符串中画了一片固定大小的区域，把它慢慢往后移动，就像滑动的窗户一样。这样就能以O(n)的时间复杂度完成这道题目。
这是它最初的样子，让人看到恍然大悟，且一秒钟就能理解。
但是现在，它又不一样了。
现在的版本
先看题：定长子串中元音的最大数目
我的第一版本的做法就和上面一致：直接滑窗，然后傻傻的又开了一个循环数里面元音的个数。
毫无意外，O(n^2)的复杂度，超时了。
百思不得其解，我去看题解，发现我已经落后于时代。现在的做法是这样的：
将滑动的窗户看成一个队列，当窗户向后滑一格时，把出去的那一格元素认为是出队；相反，滑进来的那一格元素认为是入队。如果出队的那一格元素是元音，那就将窗户当前的元音数量减一；如果进来的那一格元素是元音，那就把窗户当前的元音数量加一。因为窗户在滑动的过程中，除了出去的元素和进来的元素，其他元素都待在窗户里面，和上一次一样，都属于这个窗户，所以不需要去管它们的状态。当然，第一次进入循环的时候，还是得老老实实数元音的个数，不过就这一次，窗户向后滑之后，就只需要用上面的方法，管进来的和出去的就行了。最后时间复杂度O(n)，轻松解决。
这个做法是非常通用的，如果具备一定的应变能力(到底啥是应变能力，你下面就知道了)，它能解决90%的定长滑窗题目(计数或者求和等)。
奉上我的AC代码(最近在重温go语言，所以用go写的，当C语言看就行了，一样的)：
func isYuan(b byte) bool {//判断是否是元音的函数
return b == 'a' || b == 'e' || b == 'i' || b == 'o' || b == 'u'
}
func maxVowels(s string, k int) int {
maxCnt := 0//维护一个最大元音个数的计数器
cnt := 0//维护一个当前元音个数的计数器
for i := 0; i <= len(s)-k; i++ {
ns := s[i : i+k]//切片，切出窗户
if i == 0 { //计算第一个窗口的元音个数
cnt = 0
for j := 0; j < k; j++ {
if isYuan(ns[j]) {
cnt++
}
}
} else {
if isYuan(s[i-1]) { //如果出去的是元音
cnt-- //当前元音个数减一
}
if isYuan(s[i+k-1]) { //如果进来的是元音
cnt++ //当前元音个数加一
}
}
maxCnt = max(maxCnt, cnt)//维护一个最大元音个数
}
return maxCnt
}还能配合哈希使用
先看题：几乎唯一子数组的最大和
我先说人话翻译一下这个题目：滑窗，如果这个窗户内的元素种类>=m，那就求它的和，然后找所有满足这个条件的窗户内的和的最大值。
有什么东西能够自动去重，并且能够快速查询想要的元素？那就是哈希。在各类编程语言中，都有相对应的使用了哈希的容器。Python是字典(dict)和集合(set)，cpp和go中是映射(map)。
将数据以哈希的形式存放，查询它是否存在、查询它对应键值对的值、删除它等操作的时间复杂度平均下来都是O(1)，非常快。
在这道题目中，我们继续套用上面的滑窗逻辑，将它和map相结合：
map容器的长度就是元素种类的个数，因为是键值对，还能顺带统计每个种类元素的数量。
对于出窗户的元素，将它在map中的值减一，如果已经是1，那就将它从map中删除；对于入窗户的元素，如果已经存在于map中，那就将它在map中的值加一，如果不存在，就用该元素创建一个键，指向1。这样我们就完成了在滑窗时，哈希的处理。
题目还要求我们求和，那只需要我们用上面的老方法一直维护一个和就行了。当map的长度达到要求，说明这个窗户的和有资格参加最大和的竞争，此时才去拿他和一个一直在维护的最大和去比较。
这样跑下来，时间复杂度O(n)，完美过所有数据。
Talk is cheap, show you my code:
func maxSum(nums []int, m int, k int) int64 {
hash := make(map[int]int)//用于统计元素种类和各种类元素数量的哈希容器，并且具备自动去重功能
var maxxSum, curSum int64//初始化最大和、当前和
for i := 0; i <= len(nums)-k; i++ {
if i == 0 { //第一次进入，做好初始化工作
for j := 0; j < i+k; j++ {//正常初始化当前和，以及哈希容器
_, ok := hash[nums[j]]//检查该元素是否存在于map容器中
if ok {
hash[nums[j]]++ //如果存在，直接次数加一就行
} else {
hash[nums[j]] = 1 //如果不存在，就创建
}
}
for j := 0; j < i+k; j++ {
curSum += int64(nums[j])//此处正常累加求和
}
} else {
curSum -= int64(nums[i-1])//出窗口，减去出去元素的值
if hash[nums[i-1]] == 1 { //如果该元素次数已经只有一次了
delete(hash, nums[i-1])//直接删掉
} else {//否则次数减一即可
hash[nums[i-1]]--
}
_, ok := hash[nums[i+k-1]] //检查新加入窗口的元素是否在hash内
if ok {//如果在，次数加一
hash[nums[i+k-1]]++
} else {//否则创建
hash[nums[i+k-1]] = 1
}
curSum += int64(nums[i+k-1])//进窗口，加上进来元素的值
}
if len(hash) >= m {//如果map容器的长度，即元素种类的数量达到了m个的要求
maxxSum = max(maxxSum, curSum)//说明该窗户内的元素有资格参与最大和的竞争，维护一个最大和
}
}
return maxxSum
}随机应变这一块
先看题：可获得的最大点数
一看到这个题，我第一反应是用双指针去做(差不多就是在两端放指针，哪边大就取那边)，但是我很快发现了问题，怎么也想不出来。
一看题解，我傻了：这不就是反过来的滑动窗口吗？？？
做法是这样的：
我们要让只能两端取牌的总点数最大，而且能取牌的个数固定，那就是相当于找一个(总长度-取牌个数)长度的滑窗，使这个滑窗的和最小，再用总和减去这个最小的和，相当于剩下的就是最大的。
所以第一步，遍历整套牌，算出总点数。
第二步，用(总长度-取牌个数)长度的窗户正常滑窗，维护出一个最小和。
第三步，用总点数减去这个最小和，得到答案。
代码是这样的，我说的已经很清楚了，就不注释了：
func maxScore(cardPoints []int, k int) int {
minWindowSum := int(10e9)
curSum := 0
//1.先计算出总点数
totalPoints := 0
for i := 0; i < len(cardPoints); i++ {
totalPoints += cardPoints[i]
}
//2.开始滑窗
l := len(cardPoints) - k
for i := 0; i <= k; i++ {
if i == 0 { //初次进入
for j := 0; j < l; j++ {
curSum += cardPoints[j]
}
} else {
curSum -= cardPoints[i-1]
curSum += cardPoints[i+l-1]
}
minWindowSum = min(minWindowSum, curSum)
}
return totalPoints - minWindowSum
}还有一些很阴的题目
看题，我就简单讲讲：爱生气的书店老板
这道题还是有一些弯弯绕的，当然本质逻辑还是那一套滑动窗口。我想了挺久，最后才想出来去同时维护快乐时和生气时的顾客快乐总数，最后也是没看题解做出来了。这里我就直接贴代码了，注释详细一点，就不放文字版的做法了：
func maxSatisfied(customers []int, grumpy []int, minutes int) int {
var maxSum, happySum, normalSum, total, curSum int
//1.先求正常情况下感到满意的顾客人数
for i := 0; i < len(customers); i++ {
if grumpy[i] == 0 { //只有老板不生气时，才加上该时段的顾客人数
total += customers[i]
}
}
//2.然后开始滑窗
for i := 0; i <= len(customers)-minutes; i++ {
if i == 0 { //初次进入
for j := 0; j < minutes; j++ {
happySum += customers[j] //维护一个快乐的和，一直正常累加就行了
if grumpy[j] == 0 {
normalSum += customers[j] //维护正常的和，只有老板不生气时才累加
}
}
} else {
happySum -= customers[i-1] //用正常滑窗方法维护这个和就行了
happySum += customers[i+minutes-1]
if grumpy[i-1] == 0 { //如果出窗户时，老板没生气
normalSum -= customers[i-1] //那么说明我正常的和是加了这个时段的顾客数量的，得把它减去
}
if grumpy[i+minutes-1] == 0 { //同理
normalSum += customers[i+minutes-1]
}
}
curSum = total - normalSum + happySum
//正常总和-现在的正常和+把魔法用在此处的顾客和=在当前位置使用魔法的不生气顾客和
maxSum = max(maxSum, curSum) //维护一个最大不生气顾客和
}
return maxSum
}还有一道题，先看题：拆炸弹
这题的弯弯绕稍微少一些，如果一定要说哪里比较阴，那就是循环取元素和边界的判断。前者倒是还好，我一开始就想到将这个密码*2，后者找边界是真的恶心，花了我不少时间，好在只要能过用例，说明边界就找对了。
看代码：
func decrypt(code []int, k int) []int {
doubleCode := append(code, code...)//将密码*2
if k == 0 {//处理k为0的情况
var ret []int
for i := 0; i < len(code); i++ {
ret = append(ret, 0)
}
return ret
}
var st, curSum int
var pwd []int
if k < 0 {//处理k<0的情况
st = len(code) - 1
k = -k
for i := st; i < len(doubleCode)-1; i++ {//找边界后正常滑窗就行了
if i == st { //第一次进入
for j := i - k + 1; j <= i; j++ {
curSum += doubleCode[j]
}
} else {
curSum -= doubleCode[i-k]
curSum += doubleCode[i]
}
pwd = append(pwd, curSum)
}
} else {//处理k>0的情况
st = 1
for i := st; i <= len(code); i++ {//找边界后正常滑窗就行了
if i == st { //第一次进入
for j := i; j < i+k; j++ {
curSum += doubleCode[j]
}
} else {
curSum -= doubleCode[i-1]
curSum += doubleCode[i+k-1]
}
pwd = append(pwd, curSum)
}
}
return pwd
}2.不定长滑动窗口
2.1.求最长/最大
顾名思义，这一部分的题目就是求最长的满足某个要求的子串或者最大/最小的某个值。滑窗的做法大体有3种，题型也有好几种，放在下面说。先说滑窗的做法：
第一种 直接型 时间复杂度O(n^2)
基本原理是这样的：
使用双重循环。第一层（最顶上）的主循环负责管理滑窗的左边界，内侧的子循环负责管理滑窗的右边界。右边界的指针从左边界开始，一直到最右侧结束，即每次的主循环的窗户，都是左边界不变，右边界在一直往右。下一次主循环再将左边界往右推一格，如此往复。这样就相当于枚举到了窗户的每种情况，时间复杂度O(n^2)。
看代码：
s:="slidingwindowisgreatlol"//这是你要滑的窗户，也可以是数组
for i := 0; i < len(s); i++ {
for j := i; j < len(s); j++ {
//在这里处理逻辑，i是滑窗的左边界，j是右边界
}
}这种方法几乎所有题目都能用，因为这就是不定长滑窗的暴力枚举法，除非题目对时间复杂度要求比较高，那就只能搬出下面的办法了。
能用该方法解决的几道题目：
我挑第一道题目讲讲。先读题：3. 无重复字符的最长子串
解题思路如下：
首先看到不含有重复字符，就想到利用哈希表；最长子串，就想到不定长滑动窗口。我们直接用上面的方法枚举每一个窗口，当右指针往右移动时不断往map里面加元素，并时刻检查map的长度是否等于窗口的长度，如果等于，就将此次窗口长度和最大值比较，并继续往后；如果不等于，说明已经有缺口了，往后也补不上，直接break右移左边界，如此往复。最后维护出来的最大值就是答案。顺带一提，这道题目也可以用第二种方法做，只是它用例给了放水的空间，那不得不放。
看代码：
func lengthOfLongestSubstring(s string) int {
maxLength := 0 //初始化最大长度
for i := 0; i < len(s); i++ { //遍历左边界
hash := make(map[byte]int) //初始化哈希表（每次更新左边界时都要作废）
for j := i; j < len(s); j++ { //遍历右边界
hash[s[j]]++ //直接统计数量（go的map，如果传入不存在的key，默认返回对应类型的0值）
if len(hash) < j-i+1 { //如果种类小于长度，直接退出
break
} else {
maxLength = max(maxLength, j-i+1) //否则维护最长长度
}
}
}
return maxLength
}直接O(n^2)极限过测（我这个break但凡删除，就过不了测）。
第二种 条件移动左边界型 时间复杂度O(n)
基本原理是这样的：
只遍历滑窗的右边界。向右扩大滑窗，左边界一直不动，同时一直做符合题目要求的某种统计（计数等）。如果这个滑窗满足条件，就一直更新它的最大长度；如果不满足条件了，那就把左边界一直往右推，缩小滑窗，直到满足条件，如此往复。
看代码：
maxLength := 0
l := 0 //左边界
for r := 0; r < len(nums); r++ { //遍历右边界
//在这里处理逻辑
for hash[nums[r]] > k { //一直移动左边界，直到符合条件为止
//处理逻辑
l++
}
}这种方法的好处就是很快，时间复杂度O(n)，坏处就是不一定所有题目都能用。
能用该方法解决的几道题目（也可以说是必须要用该方法解决的题目）：
我挑第二题讲讲，先看题：1004. 最大连续 1 的个数 III
思路如下：
看到题目中说最多可以把k个0变成1，还要求连续1子串的最大长度，说明我们滑的窗户需要符合：窗户中0的个数必须<=k。这样就好办了。我们直接起一个map或者数组或者两个变量都行，来统计0和1的个数，不断往右推右边界扩大窗户；一旦0的个数超过了k，此时无论右边界怎么往右推都无法挽回了（0的个数只会多或者不变，不会少），那就开始向右推左边界，缩小窗户，直到0的个数符合条件，统计下此时的长度，和最大值比较。最后输出最大值即可。
看代码：
func longestOnes(nums []int, k int) int {
cnt := []int{0, 0} //计数数组
maxLength := 0 //维护最大长度
l := 0 //左边界
for r, v := range nums { //向右推右边界
cnt[v]++ //计数
for cnt[0] > k { //不符合条件了
cnt[nums[l]]-- //右推左边界时维护计数，用于判断个数是否符合条件
l++ //右推左边界
}
maxLength = max(maxLength, r-l+1) //记录最长长度
}
return maxLength //返回最大长度的答案
}时间复杂度O(n)，轻松过测。
第三种 二分查找+定长滑窗型 时间复杂度O(nlogn)
基本原理是这样的：
将二分查找和定长滑窗相结合。用二分查找去找到一个合适的长度，再去用定长滑窗验证这个长度是否符合某个条件。再通过验证的结果去调整长度的大小。只有在“长度越长或者越短，越难以达成条件”的题目上可以使用，一般只会用前两种方法。
看代码：
ans := 1 //初始化存储答案的变量
answerKey := "slidewindowonme"
l, r := 0, len(answerKey) //初始化长度的左右边界
for l <= r {
curLength := (l + r) / 2 //二分当前去尝试的长度
for i := 0; i <= len(answerKey)-curLength; i++ { //定长滑窗去尝试
if i == 0 {
for j := 0; j < curLength; j++ {
//在这里处理初次进入时的逻辑
}
} else {
//处理后续进入时的逻辑（出窗咋整、进窗咋整）
}
if 符合条件 {
break //因为我们只需要验证这个长度可行就可以了，不需要继续遍历后面，节约时间
}
}
if 符合条件 { //从定长滑窗的循环中退出来后，判断的语句应该是和上面一模一样的，此时就可以按照需求调整长度的大小了
ans = curLength //记录下答案
l = curLength + 1 //去尝试更长的长度
} else {
r = curLength - 1 //尝试更短的长度
}
}
fmt.println(ans) //输出的就是答案由于符合上述条件的题目不多，我目前只找到一道题目可以用这个方法极限过测（速度超过5%的人），甚至我还写了一个题解，感兴趣的可以去看看，就不在这里展开这道题目了。
这道题目是：2024. 考试的最大困扰度
2.2.求最短/最小 250730
好久不见，连着20天没更新是因为我出去玩了，现在回家了，有时间刷题了，接着补上。
求最短/最小类型的滑动窗口的题目，和上面一样，我大致分成3种方法。
第一种 暴力型 时间复杂度O(n^2)
这个方法和2.1的直接型有些不同，2.1是暴力枚举左右边界，而这里是暴力枚举滑窗的长度，然后在内层循环进行定长滑窗。
当然时间复杂度都是一样的。
我直接对着这道题来讲讲这个方法，先看题：2904. 最短且字典序最小的美丽子字符串
提取要素：子串+计数，一眼滑窗。因为长度越短越好，所以外层循环从小到大，一旦找到了直接break退出就行。
func shortestBeautifulSubstring(s string, k int) string {
ans := ""
flag := false
for curLength := 1; curLength <= len(s); curLength++ { //外层循环遍历长度，从小到大
cnt := 0 //“1”的计数器
for i := 0; i <= len(s)-curLength; i++ { //内层循环是经典的定长滑窗，不会的看上面的1.1，此处不再赘述
if i == 0 {
for j := 0; j < curLength; j++ {
if s[j] == '1' {
cnt++
}
}
} else {
if s[i-1] == '1' {
cnt--
}
if s[i+curLength-1] == '1' {
cnt++
}
}
if cnt == k && (ans == "" || s[i:i+curLength] < ans || curLength < len(ans)) {
//这个取结果的条件比较复杂：只有1的数量达到题目要求，并且符合以下的条件之一(初次进入、字典序更小、长度更短)，才能取出作为结果
//PS：这里其实长度更短的条件可以不写，因为滑窗本身就是定长的，找到了就退出了，不会去找后面更长的子串
ans = s[i : i+curLength] //切片取出结果
flag = true //flag作为标识符，用于提前退出循环
}
}
if flag {
break //在此处使用flag判断是否已经找到了结果
}
}
return ans
}这道题的用例比较水，即使用暴力枚举左右边界的方法应该也是能通过的，感兴趣的同学可以自己试试。
第二种 主流法 时间复杂度O(n)
简单讲讲这个方法：
初始化左边界为l，开一个for循环枚举右边界r，并一直检查这个窗口是否满足某个条件，一旦检测到满足条件，就进入子循环，将左边界l一直往右推，以此来缩小窗口，并一直检查该窗口是否还是符合某个条件，一旦不符合就退出循环，停止左边界的前推。这里有一个很重要的点，就是在大多数循环结构中，只有当左边界l已经把窗户缩小到不符合条件的状态下，才会触发退出循环的条件来退出循环。所以在取最短的、符合条件的区间时，需要将左边界l左推一格，这样才是完整的区间。此时不需要真的去动这个左边界l，我们只需要在取出这个边界时，用[l-1:r+1]这个区间即可，否则如果你将左边界推回去了，破坏了这个恰好的错位状态，下一次外层循环回来，进行是否满足条件的判断时，又会判断满足条件，从而陷入死循环。所以这样正好。
叽里咕噜说了这么多，我在说啥你估计也没看懂，那就看看代码吧：
func slidingWindow(s string) string {
l := 0
ans := "" //初始化存储答案的变量
for r := 0; r < len(s); r++ {
//在这里进行你的计数等等的算法逻辑
if 符合条件 {
for 符合条件 && l <= r { //并且左边界要小于等于右边界，否则会越界
//在这里进行你的计数等等的算法逻辑
l++ //右移左边界，缩小窗口
}
if 符合条件 {
ans = s[l-1 : r+1] //如上面所说，左边界取的时候需要左撤一格
ansLen = r - l + 2
}
}
}
return ans
}这个方法其实和上面2.1的第二种方法很像，但是有本质区别：2.1的第二种方法是在我计数或者干啥时，已经开始不符合某个条件了，并且此时只有缩小窗户才能使其回到正轨，右移右边界扩大窗户只会让它变得更糟。所以我右移左边界来缩小窗户是为了亡羊补牢。但是这个方法就不一样了，我是想找到最短的、并且符合条件的子串，我一开始先右移右边界扩大窗口，直到满足条件，然后此时我右移左边界是为了在满足条件的前提下找到更短的子串。这就是这两个用在不同题型下的不同方法的本质区别。
下面来几道题目讲讲，难度逐级递增(1个中等2个hard)，没有一题是直接套用这个算法就完事的。方法本身是不难，但是在套用这个方法之前，对于题目条件和要求的转化还是比较有难度的。
第一题：2875. 无限数组的最短子数组(中等难度)，先看题。
看完题了吧？第一次看完这道题的时候，我也是一头雾水。我猜到你一定会有以下难点：
1.这个“无限”数组的长度，我该如何确定？总不可能每个用例都顶着给出的用例数据量范围来给这个数组拼接个10的好多次方个吧？这样早就爆内存了。
2.数据量这么大，就算我找到了确定这个数组长度的方法，那我即使用这个时间复杂度O(n)的滑窗方法对着拼接出来的无限数组滑，也会超时吧？
现在让我们来逐一解决这两个问题。当然，我当时也是没想出来要咋整，去看了题解，理解了之后自己做出来的。
首先，我们不需要确定这个无限数组的长度。能问出这两个问题，说明你的思考方向不对。数据量非常大，单个数组的长度就有可能达到10^5，而target更是可能达到10^9，直接拼接肯定是不行的。既然这个窗口有可能跨越很多个一模一样的数组，说明它有周期性，那我们是不是可以用乘法来代替无用的重复拼接？
将target整除数组的和，就能得到它结果的窗户所需要用到的数组的数量；更进一步，我们将target对数组的和取余，是否就得到了真正变幻莫测，需要我们去滑窗的，在周期之外的剩下的东西？并且这个leftover的值一定是比数组的和要小的。
但是这是否代表着我们直接对单个数组滑窗就行了？不行。因为这样会忽略首尾相接的情况。
所以直接把原数组double一下，对着这个新的doubleNums滑窗就行了，能覆盖到全部情况。
思路讲完了，看代码：
func minSizeSubarray(nums []int, target int) int {
//1.计算单个nums的和
sum := 0
for _, v := range nums {
sum += v
}
//2.计算目标相对于和的余数
left := target % sum //这是周期外剩下的东西
extra := target / sum //这是组成结果所需要用到的数组的数量
if left == 0 { //如果能被整除，说明没有剩下的东西
return len(nums) * extra //有几个数组，长度就是数量*每个数组的长度
}
//3.滑窗寻找和是left的最短子串
l := 0 //初始化滑窗的左边界
total := 0 //初始化累加变量
doubleNums := append(nums, nums...) //将数组复制一份，拼接到自己的后面，实现double
minLength := len(doubleNums) //用于记录最小长度
for r := 0; r < len(doubleNums); r++ { //不定长滑窗，套用上面的方法
total += doubleNums[r] //累加求和
for total >= left && l <= r { //触发条件了，开始缩小窗户
if total == left { //满足条件了，记录下最短长度
minLength = min(minLength, r-l+1)
}
total -= doubleNums[l] //缩小窗户
l++
}
}
if minLength == len(doubleNums) { //如果最小长度依然处于初始值，说明没更新过这个变量
return -1 //那就是没找到，返回-1
}
//3.计算结果
return extra*len(nums) + minLength //数组个数*每个数组的长度+算出来的滑窗长度(余数所对应的滑窗长度)，得到答案
}第二题：76. 最小覆盖子串(hard难度)，先看题。
翻译一下题目，就是：先统计t字符串中每个元素的个数，然后你需要在s中找到一个子串，这个子串中必须包含t字符串中的所有元素，并且对应元素的个数必须大于等于它在t字符串中的个数。这个你看用例也能比较清楚的理解。
要素察觉：统计种类和个数，哈希和数组二选一；最短子串，不定长滑窗。
那么我们就有了一个基本流程：先用map映射统计t字符串中每个元素的个数，然后再开不定长滑窗：不断右移右边界，直到涵盖了全部元素，再右移左边界直到不涵盖全部元素，然后在切片取结果时左撤一步左边界，记录下长度，再根据长度是否更短来决定后续是否要更新结果。
那么我们该如何判断是否涵盖呢？我是采用了开一个for循环来逐一对比的方法：遍历统计t字符串元素数量的cnt1字典的键和值，再将键代入动态统计当前窗户元素数量的映射cnt2中，判断其数量是否大于等于cnt1中当前值的数量，一旦发现小于，直接return false，只有全部遍历过去都是>=，最后退出循环后才会return true。
方法就是这样，直接看代码。滑窗的部分我就不注释了，和上面的逻辑一模一样。
func isCovered(c1 map[byte]int, c2 map[byte]int) bool { //判断是否涵盖的函数
for k, v := range c1 { //遍历统计s元素数量的映射
if c2[k] < v { //一旦当前窗口内该元素的数量小于s中该元素的数量
return false //直接返回false
}
}
return true //全部通过才返回true，说明涵盖了
}
func minWindow(s string, t string) string {
//1.先统计目标的种类数量
cnt := make(map[byte]int)
for _, v := range t {
cnt[byte(v)]++ //顺带一提，go的映射，没涉及到的键，默认值都是对应数据类型的零值，所以可以直接加，不需要判断键是否存在
}
//2.再滑窗
l := 0
cnt2 := make(map[byte]int) //记录当前窗口内元素的种类用
ans := ""
ansLen := len(s) + 1
for r := 0; r < len(s); r++ {
cnt2[s[r]]++
if isCovered(cnt, cnt2) {
for isCovered(cnt, cnt2) && l <= r {
cnt2[s[l]]--
l++
}
if r-l+2 < ansLen {
ans = s[l-1 : r+1]
ansLen = r - l + 2
}
}
}
return ans
}第三题：632. 最小区间(hard难度)，先看题。
这题的方法有很多种，我的方法貌似又是标新立异那一个，在题解里没看到熟悉的影子。
受前面几道题的启发，我想的是把这个nums给拆了，拼在一起，然后再起一个新数组newNumsIndex来存放每个数字所属的组别(类似[1,1,1,2,2,2,3,3,3..]这样的)，然后将拼在一起的newNums升序排序，让这个newNumsIndex和它联动排序。最后在这个newNumsIndex中进行不定长滑窗：用映射map统计当前窗户里面的元素种类，不断右移右边界，直到种类数量(len(map))和组数(len(nums))相等，就尝试缩小左边界，直到二者不相等后停下，记录下当前的左边界和右边界，以及两个边界之间的跨度，后续只有跨度更小或者跨度相等但是左边界更小的值才能替换掉当前的左右边界。
type numIndexSorter struct {
nums []int
indices []int
}
func (s numIndexSorter) Len() int {
return len(s.nums)
}
func (s numIndexSorter) Less(i, j int) bool {
return s.nums[i] < s.nums[j]
}
func (s numIndexSorter) Swap(i, j int) {
s.nums[i], s.nums[j] = s.nums[j], s.nums[i]
s.indices[i], s.indices[j] = s.indices[j], s.indices[i]
}
//上面都是go语言特性，需要实现Len(),Less(),Swap()三个方法，并且构建结构体，才能用内建库sort进行两个数组的自定义联动排序
//如果仅仅是关注算法可以不用看上面的内容
func smallestRange(nums [][]int) []int {
var newNums, newNumsIndex []int
//1.先把数组拆了，排序
for idx, v := range nums {
newNums = append(newNums, v...) //将数组内部的元素拆开并在一起
for i := 0; i < len(nums[idx]); i++ {
newNumsIndex = append(newNumsIndex, idx+1) //生成每个元素的组号
}
}
sorter := numIndexSorter{nums: newNums, indices: newNumsIndex} //升序联动排序
sort.Sort(sorter) //升序联动排序
//2.开始滑窗
cnt := make(map[int]int) //初始化计数器
l := 0 //初始化左边界
ans := []int{0, 0} //存放左右边界的变量
ansLength := newNums[len(newNums)-1] - newNums[0] + 1 //初始化长度
for r := 0; r < len(newNums); r++ { //滑窗，此处就不讲解了，逻辑和上一道题一模一样
cnt[newNumsIndex[r]]++
if len(cnt) == len(nums) {
for len(cnt) == len(nums) {
cnt[newNumsIndex[l]]--
if cnt[newNumsIndex[l]] == 0 { //由于我们要统计种类，所以如果该键数量归零了就要删除，否则还是会被计入len
delete(cnt, newNumsIndex[l])
}
l++
}
if newNums[r]-newNums[l-1] < ansLength ||
(newNums[r]-newNums[l-1] == ansLength && newNums[l-1] < ans[0]) {
//这里是完全按照题目的定义来写的判断
ans = []int{newNums[l-1], newNums[r]}
ansLength = ans[1] - ans[0]
}
}
}
return ans
}第三种 二分查找+定长滑窗型 时间复杂度O(nlogn)
这里的二分+定长滑窗就和2.1的逻辑基本一样了，只不过这里是遇到困难了去尝试更长的长度，2.1是遇到困难了去尝试更短的长度。
基本框架：
ans := 1 //初始化存储答案的变量
answerKey := "slidewindowonme"
l, r := 0, len(answerKey) //初始化长度的左右边界
for l <= r {
curLength := (l + r) / 2 //二分当前去尝试的长度
for i := 0; i <= len(answerKey)-curLength; i++ { //定长滑窗去尝试
if i == 0 {
for j := 0; j < curLength; j++ {
//在这里处理初次进入时的逻辑
}
} else {
//处理后续进入时的逻辑（出窗咋整、进窗咋整）
}
if 符合条件 {
break //因为我们只需要验证这个长度可行就可以了，不需要继续遍历后面，节约时间
}
}
if 符合条件 { //从定长滑窗的循环中退出来后，判断的语句应该是和上面一模一样的，此时就可以按照需求调整长度的大小了
ans = curLength //记录下答案
r = curLength - 1 //去尝试更短的长度
} else {
l = curLength + 1 //尝试更长的长度
}
}
fmt.println(ans) //输出的就是答案能用这个方法解决的两道题目：
1.1234. 替换子串得到平衡字符串。这题和1423. 可获得的最大点数特别像，都是反过来的滑窗，只不过后者是定长滑窗，这个是不定长滑窗而已。直接看代码：
func conv(b byte) int { //由于我是用数组当映射来计数，所以需要这个函数来把字母转换成其对应的下标
if b == 'Q' {
return 0
}
if b == 'W' {
return 1
}
if b == 'E' {
return 2
}
if b == 'R' {
return 3
}
return 0
}
func balancedString(s string) int {
n := len(s) / 4
cnt := []int{0, 0, 0, 0}
//1.先统计整体的个数
for i := 0; i < len(s); i++ {
cnt[conv(s[i])]++
}
//这一块代码是为了判断是否已经平衡，这样就不用进行后面的逻辑了
flag := true
for i := 0; i < 4; i++ {
if cnt[i] != n {
flag = false
break
}
}
if flag {
return 0
}
//2.开始滑窗尝试
ans := 0
l := 1
r := len(s)
for l <= r { //二分查找找长度
length := (l + r) / 2
cnt2 := []int{0, 0, 0, 0}
for i := 0; i <= len(s)-length; i++ { //经典定长滑窗
if i == 0 {
for j := 0; j < length; j++ {
cnt2[conv(s[j])]++
}
} else {
cnt2[conv(s[i-1])]--
cnt2[conv(s[i+length-1])]++
}
flag := true
for idx, v := range cnt2 {
if cnt[idx]-v > n {
flag = false
break
}
}
if flag { //符合条件
ans = length
break
}
}
if ans == length { //符合条件
r = length - 1 //尝试更短的
} else {
l = length + 1
}
}
return ans
}2.209. 长度最小的子数组。这题的用例特别水，看官方题解，暴力法也能过(Python不行哈哈哈)。和上面一模一样的二分+定长滑窗，我就不注释了。
func minSubArrayLen(target int, nums []int) int {
l := 1
r := len(nums)
ans := 0
for l <= r {
curLength := (l + r) / 2
curSum := 0
for i := 0; i <= len(nums)-curLength; i++ {
if i == 0 {
for j := 0; j < curLength; j++ { //首次进入
curSum += nums[j]
}
} else {
curSum -= nums[i-1]
curSum += nums[i+curLength-1]
}
if curSum >= target {
ans = curLength
r = curLength - 1
break
}
}
if curSum < target {
l = curLength + 1
}
}
return ans
}2.3.求子数组个数
2.3.1.越长越合法 250731
像这个系列，我也是刷了5道题目，其中前3道纯纯的公式化，后2道比较有难度(一道中等，一道hard)，也就是我得经过一些弯弯绕才能运用这个方法来解决问题，或者换个说法，和这个方法结合的其他做法比较难以想到。先来讲讲解决这一系列题目最基本的方法，有且只有一种，和上面2.2的主流法基本一致，是这个方法的延伸：
和2.2的主流法一样，先准备一个left作为左边界，然后开个循环遍历right右边界，正常处理算法逻辑，然后在循环内开一个子循环，时刻检测窗口是否符合题目条件，一旦突然符合了，就进入这个子循环开始右推左边界，直到不符合后停下。此时，[left,right]这个区间已经是不符合条件的了，但是[left-1,right],[left-2,right]...[0,right]全都是符合条件的，这些都是子串，这就是“越长越合法”这个说法的来源。所以，我们可以计算出，此时符合条件的子串一共有0->left-1，一共left个。在退出当前子循环后，我们直接将计数器cnt+=left，右边界right继续右推，然后又进子循环，如此往复...这样，我们就很精妙的，在O(n)的复杂度内，算出了符合要求的子串的个数。
看一下基本代码模板(直接复制粘贴无法运行，主要看代码结构)：
func 求子数组个数(s string) int {
counter := 0 //初始化子数组个数的计数器
l := 0 //初始化窗口的左边界
for r := 0; r < len(s); r++ { //遍历右边界
//在这里处理算法逻辑，例如映射的累加
for 符合条件 {
//在这里处理算法逻辑，例如映射的累减等
l++ //右推左边界
}
counter += l //计数器累加子串个数
}
return counter
}这个模板贯穿这五道题，或直接套用，或有些弯弯绕，但是最终都是要用到它。
下面开始讲题。由于前三题就是简单的直接套用，所以我挑其中一道题简单讲讲：3325. 字符至少出现 K 次的子字符串 I，先看题。
我翻译一下题意：给你字符串s和整数k，你需要统计当前子串中有没有元素的出现次数是大于等于k的，如果有就符合条件，计数记下来。
要素察觉：子串->不定长滑窗，统计种类->哈希表。我们可以写一个函数判断传入的子串(将统计子串的映射计为cnt)是否满足至少有一个字符至少出现 k 次这个条件，然后把这个函数套在这个框架里面就行了。
至于这个函数怎么写，倒也不难，就是遍历cnt的值，比较这个值是否大于等于k，只要有一个满足，就可以直接返回true，全都不满足才返回false。
思路讲完了，上代码：
func timesOk(cnt map[byte]int, k int) bool { //检查是否符合题目条件的函数
for _, v := range cnt { //遍历映射的值
if v >= k { //只要有一个达标就行了
return true
}
}
return false
}
func numberOfSubstrings(s string, k int) int { //主函数
cnt := make(map[byte]int) //统计子串的映射(哈希表)
l := 0 //左边界
counter:=0 //计数器
for r := 0; r < len(s); r++ { //向右推右边界
cnt[s[r]]++ //统计各元素的数量
for timesOk(cnt,k){ //子循环判断元素出现次数是否达标
cnt[s[l]]-- //减去出窗口元素的个数
l++ //右推左边界
}
counter+=l //加上从0->l-1一共l个子串
}
return counter
}另外两道题比这道题略简单一些，可以直接秒：
接着我们来过一下比较难的两道题，首先是第一题：3298. 统计重新排列后包含另一个字符串的子字符串数目 II ，先看题。
主要难点：用例卡哈希，用映射map过不了，用数组却能险过。遇到这种情况，可能大多数人都以为是自己的方法不对，然后去换方法，最后弄的焦头烂额想不出来。其实力扣真的挺恶心的，有时候就是会卡你一些莫名其妙的东西。
思路就不在这里重复了，想看详细思路去上面2.2看76题的做法，再回来看这里的代码就会了。这题其实就是76. 最小覆盖子串的做法加上这次的子数组个数框架，然后把哈希换成数组来计数就能过。
func isCovered2(word2C []int, subC []int) bool { //和76题一样，判断是否“涵盖”
for k, v := range word2C { //遍历统计word2元素种类及其个数的映射
if subC[k] < v { //比较子串的所有元素的个数是否全都大于等于word2中的元素
return false //有一个小于直接全盘否定，返回false
}
}
return true //全部通过才能返回true
}
func validSubstringCount(word1 string, word2 string) int64 {
//1.先统计word2
word2Cnt := make([]int, 26) //初始化26格的数组，用于统计word2中小写字母数量
for _, v := range word2 { //统计word2的元素种类和数量
word2Cnt[byte(v)-'a']++
}
//2.开始滑窗
subCnt := make([]int, 26) //初始化26格的数组，用于统计子串中小写字母数量
l := 0 //初始化左边界
var count int64 //为了防止爆int，特意将计数器初始化为int64
for r := 0; r < len(word1); r++ { //求子数组个数滑窗模板
subCnt[word1[r]-'a']++
for isCovered2(word2Cnt, subCnt) {
subCnt[word1[l]-'a']--
l++
}
count += int64(l)
}
return count
}接着是第二题：2537. 统计好子数组的数目，先看题。
这道题还是比较有难度。
一开始我想了一阵子，想到了用组合数：C<相同数的个数>取2，不就是题目所要求的pair的数量吗？这样我就只需要用hash统计每个元素的数量，然后各自取组合数然后累加不就行了？我立刻行动，写下了第一版代码，然后直接粘贴进力扣试用例：居然全过了，难道说...
于是我直接提交，等力扣测评，结果也是不出意外的超时了，时间复杂度O(n^2)。
没招了，我直接去看题解，题解的方法又是我从来没见过的一种：
核心思路：
如果窗口中有 c 个元素 x，再进来一个 x，会新增 c 个相等数对。
如果窗口中有 c 个元素 x，再去掉一个 x，会减少 c−1 个相等数对。
用一个哈希表 cnt 维护子数组（窗口）中的每个元素的出现次数，以及相同数对的个数 pairs。外层循环：从小到大枚举子数组右端点 right。现在准备把 x=nums[right] 移入窗口，那么窗口中有 cnt[x] 个数和 x 相同，所以 pairs 会增加 cnt[x]。然后把 cnt[x] 加一。
内层循环：如果发现 pairs≥k，说明子数组符合要求，右移左端点 left，先把 cnt[nums[left]] 减少一，然后把 pairs 减少 cnt[nums[left]]。
内层循环结束后，[left,right] 这个子数组是不满足题目要求的，但在退出循环之前的最后一轮循环，[left−1,right] 是满足题目要求的。由于子数组越长，越能满足题目要求，所以除了 [left−1,right]，还有 [left−2,right],[left−3,right],…,[0,right] 都是满足要求的。也就是说，当右端点固定在 right 时，左端点在 0,1,2,…,left−1 的所有子数组都是满足要求的，这一共有 left 个。
最上面的核心思路是解决本题目的关键，它并不打算一次性算出数对的数量，而是尝试从窗口进出元素的变化中动态计算数对的数量。这是它打破O(n^2)时间复杂度的壁垒，将复杂度直接压到O(n)的关键。
这个核心思路相当于：将新进来的x和里面的c个x连线，会组成c个数对；将退出的那个x和剩下的c-1个x连线，会组成c-1个数对。
解决了这个核心思路，这道题目其实就和前面的公式化题目没啥区别了，直接拿下：
func countGood(nums []int, k int) int64 {
l := 0
var counter, pair int64 //前者记录子串数量，后者记录当前子串内的组数
cnt := make(map[int]int) //记录每个元素的数量
for r := 0; r < len(nums); r++ { //这就是上面的滑窗模板
pair += int64(cnt[nums[r]]) //如果窗口中有 c 个元素 x，再进来一个 x，会新增 c 个相等数对
cnt[nums[r]]++ //累加元素数量
for pair >= int64(k) {
cnt[nums[l]]-- //将出窗口的元素数量减去
pair -= int64(cnt[nums[l]]) //如果窗口中有 c 个元素 x，再去掉一个 x，会减少 c−1 个相等数对
l++ //右移左边界
}
counter += int64(l) //累加子串个数
}
return counter
}2.3.2.越短越合法 250801
这个越短越合法的求子数组个数的题目，我也是刷了5道题，大致是这样的情况：前3题直接无脑套模板，第4题稍微加点弯弯绕但不多，第5题稍微难一点。和2.3.1一样，这个“越短越合法”也是有贯穿题目始终的算法模板的，大致描述起来是这样，和2.3.1的模板及其类似：
初始化左边界left，计数器cnt。开一个循环遍历右边界right，使其一直往右推，直到不符合条件，然后进入子循环，将左边界left一直往右推，直到符合条件。此时，[left,right]这个区间已经是符合条件的了(这一点和2.3.1的方法不一样)，由于是越短越合法，所以[left+1,right],[left+2,right]...[right,right]都是合法的子数组。所以我们直接在计数器cnt上累加上right-left+1，就是我们这次得到的子数组个数。然后主循环继续将右边界向右推，直到再次不符合条件，如此往复，直到到达边界。这样我们就能在一次次的左右边界的接力前进中得到所有符合条件的子数组个数，时间复杂度O(n)。
代码框架是这样的：
func 越短越合法的求子数组个数框架(nums []int, 题目用到的其他变量 int) int {
l:=0 //初始化左边界
count:=0 //初始化计数器
for r:=0;r<len(nums);r++{ //向右推右边界
//在这里处理你题目所需的算法逻辑，例如映射累加等
for 不符合条件{ //给不懂go语言的同学们科普一下，go是没有while循环的，go的for循环后面写条件就相当于其他语言的while
//在这里处理你题目所需的算法逻辑，例如映射累减等
l++ //向右推左边界
}
count+=r-l+1 //将right-left+1累加到计数器中，获得本次循环的子数组个数
}
return count //最终获得全部子数组个数
}由于前三题过于简单，属于是直接套用就能解决，所以我挑其中最难的一道题来讲：2302. 统计得分小于 K 的子数组数目，先看题。
看完题意，你应该能马上把这个方法和这道题目关联起来。这题唯一的一个难点就是(如果一定要揪出来一个难点)：子串的长度是动态变化的，分数又和长度有关系。如果你每次都要整体把分数算出来，你还得获得这个子串上一次的长度，然后对这个整体的分数又乘又除。。。这样肯定不行。
这题，我的做法是，正常累加窗户内元素的值，正常减去出窗户元素的值，只有判断条件是否符合时才会将这个累加的值乘上当前长度(r-l+1)，实时计算出分数，去和目标值比较。这就是一个简单的乘法运算，对计算机来说，算不上任何负担，也就是对我O(n)的时间复杂度没有任何影响。我认为这还是比较巧妙的。下面是我的AC代码：
func countSubarrays2(nums []int, k int64) int64 {
l := 0 //初始化左边界
var sum, count int64 //由于数据量较大，所以另外用int64定义累加变量和计数器
for r := 0; r < len(nums); r++ { //右推右边界
sum += int64(nums[r]) //累加上进窗口的值
for sum*(int64(r-l+1)) >= k { //累加值*长度，实时计算分数并判断是否符合条件
sum -= int64(nums[l]) //减去出窗口的值
l++ //右推左边界
}
count += int64(r - l + 1) //计数器累加上本次循环算出的子数组个数
}
return count
}另外两道题目，你只需要学会这个算法模板，就能直接秒，感兴趣的同学可以去试试：
接着来讲稍微有些弯弯绕的第4题：LCP 68. 美观的花束，先看题。
这道题，其实和前面的3325. 字符至少出现 K 次的子字符串 I特别像，这两道题目的本质都是要不断去检查映射map里面的值是否全都/存在某个值 大于/小于 某个值。你要么再开个子循环检查，要么更加简单易懂，新开个函数给这个循环封装进去，这样不会破坏框架的结构，使代码的可读性更强。
所以回到这道题，其实就是需要你去用映射或者数组统计每个品种的花的数量，然后不断遍历检查其值是否全都小于题目要求的cnt值，再套进这个模板，就能秒解决。代码如下：
func isBeautiful(hash map[int]int, cnt int) bool { //检查花束是否美观的函数
for _, v := range hash { //遍历映射
if v > cnt { //只要有一个花的数量比要求值大
return false //直接否定
}
}
return true //全部都不超过要求值才能通过
}
func beautifulBouquet(flowers []int, cnt int) int { //解题主函数
l := 0 //左边界
hash := make(map[int]int) //计数的映射
count := 0 //计数器
MOD := 1000000007 //题目要求的取余的数
for r := 0; r < len(flowers); r++ { //正常公式化循环
hash[flowers[r]]++
for !isBeautiful(hash, cnt) {
hash[flowers[l]]--
l++
}
count = (count + r - l + 1) % MOD //一边累加一边取余
}
return count
}接着来讲上难度的第5题：2762. 不间断子数组，先看题。
这道题目主要的难点是：我该如何确保我的子串中任意两个数相减的绝对值都会小于等于2？直接暴力枚举吗？很明显不现实。
这个还真的给我卡住了，于是我看了一下题目的提示：
Use a set or map to keep track of the maximum and minimum of subarrays.
翻译：用集合或者映射来追踪子串的最大值和最小值。
对哦！我直接保持更新子串的最大值和最小值不就行了！只要最大值减去最小值小于等于2，那其他任意两个数相减肯定小于等于2。
此时我还不知道集合在这里的作用是啥，就按照这个提示改进了我的代码，也是直接AC了：
func notGood(hash map[int]int) bool { //维护最大值最小值，并直接判断是否符合条件的函数
max2 := 0
min2 := 1000000001
for k, _ := range hash {
min2 = min(min2, k)
max2 = max(max2, k)
}
return abs(max2-min2) > 2
//这里有个小插曲，本地的go环境有abs这个容器，但是力扣没有，直接给我报错了，没绷住。不过直接拿掉倒也没啥事
}
func continuousSubarrays(nums []int) int64 { //主程序函数
l := 0 //左边界
hash := make(map[int]int) //映射，用于计数
var count int64 //初始化计数器
for r := 0; r < len(nums); r++ { //公式化循环
hash[nums[r]]++
for notGood(hash) {
hash[nums[l]]--
if hash[nums[l]] == 0 { //由于需要看键的值来确定最大值最小值，所以出窗了需要删掉
delete(hash, nums[l])
}
l++
}
count += int64(r - l + 1) //累加
}
return count
}即使代码通过了，我还是没搞懂集合在此处的作用，还以为：直接扫描子串来确定最大值最小值不是一样的吗，数字多起来后不是集合也照样会变得很长吗。直到我去求助了o4-mini，它的回答让我醍醐灌顶：
维护一个哈希表，核心目的是让「每次滑动窗口左右边界」时都能以常数时间（或接近常数）知道当前窗口里的最小值和最大值，以及它们的计数。 如果你每次都去遍历子数组本身来找 min/max，那么：
- 子数组长度可能很大，最坏情况下遍历整个窗口每次要 O(n)；
- 在双指针滑动过程中，一共会做 O(n) 次这样的遍历，整体就退化到 O(n²)，对于 n 高达 10⁵ 的情况下肯定跑不动。
用哈希表的好处在于：
- 我们只在插入／删除元素时更新计数；
- 当前窗口由于「max−min≤2」的约束，哈希表中最多只有 3、4 个不同的 key，遍历它去算 min/max 本质上是 O(1) 操作；
- 删除时若计数变为 0，就直接从 map 里删掉，不用扫描整个窗口去确认某个值是不是已经不在窗口里了。
这样每次右指针 r 向右扩、左指针 l 向右收缩都只是对 map 做 ++/--/delete，然后扫描常数级别大小的 map 来判断是否 “notGood”，整体就是 O(n) 了。
当然，也可以用双端队列维护窗口的单调队列来分别做 min/max，和哈希表的思路一样，都是为了把查找最新 min/max 的成本摊平到 O(1)／次。
总结起来就是：这个子串可能会很长，但是受题目条件限制，里面数字的种类最多就3种。毕竟如果大于3种，这个子串的最大值-最小值肯定就大于2了，它就不符合条件了。所以，利用map的自动去重+计数特性，我们可以将原本是O(n)复杂度的扫描简化到O(1)复杂度，让题目不至于变成O(n^2)直接超时。
这样看来，滑动窗口和哈希表的关系真是紧密。从定长到不定长滑窗，哈希表从未缺席。
那么今天就讲到这里。有一说一Go语言的容器是真的挺低能的，并且用Go刷这么久题目我也刷腻了，之后我要改用cpp或者python继续刷题了。。。
2.3.3 恰好型滑动窗口 250803
先来讲讲什么是“恰好型”。前面的2.3.1和2.3.2都是子串内的某某东西越多/少越好，而这次的“恰好”就是：求某某东西的数量正好等于某个值的子串的个数。
虽然条件看起来变化很大，第一时间你可能找不到头绪。但其实我们只需要继续沿用上面2.3.1和2.3.2的方法就行了，并且怎么沿用，也有两种选择。
所以，如果你有些忘记了，请先看完上面2.3.1-2两个章节，再继续阅读下面的内容。
第一种选择：利用"越长越合法"题型的方法
先复习一下“越长越合法”的解题方法：在符合条件后不断缩小区间直到不符合条件，然后就能求出>=某个值的子数组的个数。
既然要求等于某个值的子数组个数，那我们直接求出>=某个值的子串个数，再求出>=某个值+1的子串个数，不就能直接求出等于某个值的子数组个数了吗。
用编程的说法来转述一下，就是我把求越长越合法题型的代码封装成一个函数f()，然后题目传入的数组和目标值分别为nums和target，那么我们直接return f(nums,target)-f(nums,target+1)就是答案。
这次我一共刷了4道题目，3道是用这个选择做的，还有1道是用“越短越合法”的选择做的。在这3道题目中，前2道就是公式化直接代入，第3道可能稍微有那么一点弯弯绕，所以我挑第三道讲一讲：3306. 元音辅音字符串计数 II，先看题。
要素察觉：元素出现次数->哈希表计数；子数组个数->公式化滑窗。
那么基本思路就出来了：公式化滑窗遍历字符串，如果是元音，就计数存入哈希表；如果不是，就让辅音计数器累加。最后在写子循环判断条件时，按照题目要求写条件就行了，也是十分的公式化。看代码，今天开始用c++写：
class Solution{
public:
bool isYuan(char a){ //判断当前元素是否是元音的函数
return a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u';
}
long long atLeast(string word, int k){ //滑窗的主程序
long long l = 0, fuCnt = 0, count = 0; //初始化：左边界，辅音的计数器，子数组数量的计数器
map<char, int> hash; //初始化：元音的计数器
for (int r = 0; r < word.size(); r++){ //公式化滑窗
if (isYuan(word[r])){ //如果当前元素是元音
hash[word[r]]++; //计数
}else{ //如果不是元音，那就是辅音
fuCnt++;
}
while (hash.size() >= 5 && fuCnt >= k){ //hash长度就是当前窗口内的元音种类
if (isYuan(word[l])){ //公式化出窗口累减
hash[word[l]]--;
//这里注意：cpp和go一样，某个键的值归零后如果不删除，还是会被计入长度，从而影响种类数量的判断
if (hash[word[l]] == 0){
hash.erase(word[l]); //所以要在归零后及时删除
}
}else{
fuCnt--;
}
l++; //越长越合法，加上l
}
count += l;
}
return count;
}
long long countOfSubstrings(string word, int k){ //解决题目的主程序
return atLeast(word, k) - atLeast(word, k + 1); //(>=k)-(>=k+1)
}
};第二种选择：利用"越短越合法"题型的方法
同样，先复习一下“越短越合法”题型的解题方法：一直右推右边界直到不符合条件，然后一直右推左边界直到符合条件，这样就能求出<=某个值的子数组的个数了。
那么我们直接f(nums,target) - f(nums,target-1)就行了。我只有1道题目用了这个方法：992. K 个不同整数的子数组，先看题。
要素察觉：不同整数的个数->哈希表计数；子数组个数->公式化滑窗。
解题思路和上面这道题没啥区别，我就不讲了，直接看代码：
class Solution{
public:
int atMost(vector<int> &nums, int k){ //滑窗主程序
int l = 0, count = 0; //初始化：左边界，子串计数器
map<int, int> cnt; //数字种类的计数器
for (int r = 0; r < nums.size(); r++){ //公式化滑窗
cnt[nums[r]]++; //计数
while (cnt.size() > k && l <= r){ //cnt的长度就是
cnt[nums[l]]--;
if (cnt[nums[l]] == 0){ //这里和上一题一样，归零必须删除
cnt.erase(nums[l]);
}
l++;
}
count += (r - l + 1); //越短越合法，加上r-l+1。此处括号不加也行，加上是为了可读性更好
}
return count;
}
int subarraysWithKDistinct(vector<int> &nums, int k){ //解题主程序
return atMost(nums, k) - atMost(nums, k - 1); //返回(<=k个数)-(<=k-1的个数)，就是==k的个数
}
};结语
到这里，我们滑动窗口最最基础的部分也是圆满结束了！大约使用了15天时间(纯刷题时间)，我们也只不过是完成了力扣滑窗题库题目的25%。接下来，二分查找篇再见！
PS:在写这一部分的时候，我已经开始接触二分查找了，难度也是更上一个台阶。加油吧！
