专栏简介
上一个专栏，《竞赛算法速成日记》是我为了应对大一下所到来的蓝桥杯国赛和CSP认证所临时准备所学习的算法思想，只能说是提高了广度，并没有学到精髓，在竞赛中发挥的作用并不大（蓝桥杯PyB组喜提国三，CSP认证喜提前60%）。所以，我认为确实有必要系统的，多投入一些时间去学习算法的一整套体系，来应对后面更重要的工作面试。
总体学习路线，我是参照灵茶山艾府大神的这篇文章：分享｜如何科学刷题？
我从文章中扒了一张图，大体就是这样：
算法的知识面是非常广的，我也不奢求完美完成每一个模块，力求在1年内把所有基础的题目都做完，并且每做完一个板块，就来这里更新我自认为这一块知识点的精髓内容(如果我半个月没有更新，欢迎催更~)。当然这最主要的是为了加深我自己的理解，如果能顺带帮到你，那就更好了。
所以，总结一下，这个专栏，《算法笔记》，就是我为了总结消化我所学习到的算法知识，顺带还能帮助到你一点的一个专栏。下面开始正文内容。
1.滑动窗口 250704
1.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
}1.2.不定长滑动窗口
1.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. 考试的最大困扰度
