算法知识相关（更新中）

1 前缀和

1.1 基础知识

$\bigstar$表示前$i$个位置的数字的和。常见的就是，$sum$数组下标从$1$开始，则其初始化过程为

1
2
3
for(int i=1;i<=a.size();i++){
    sum[i]=sum[i-1]+a[i];
}

$\bigstar$若$sum$数组下标从$0$开始，则其初始化过程为

1
2
3
4
sum[0]=a[0];
for(int i=1;i<a.size();i++){
    sum[i]=sum[i-1]+a[i];
}

$\bigstar$计算$i \in [l,r]$范围内数的和，则和为$sum[r]-sum[l-1]$。但！要！注意！$l-1$有可能是负数的问题！ 以及！要注意！有些题$l$和$r$是计算出来的，可能会出现$l>r$的情况，还可能出现$l$和$r$大于前缀和数组最大下标的情况！！！这些都要注意了！！！

若$sum$数组下标从$1$开始，则$[l,r]$范围内数的和为$sum[r]-sum[l-1]$

若$sum$数组下标从$0$开始，则$[l,r]$范围内数的和为
$$
num_n =
\begin{cases}
sum[r] & \text{if } l =0 \
sum[r]-sum[l-1] & \text{if }l\neq0
\end{cases}
$$
注意了！！！不一样哦！！！

$\bigstar$用前缀和数组的时候，最好用long long类型，否则有可能超过类型的范围。

1.2 扩展应用

$\bigstar$边维护前缀和数组边计算题目想要的值（涉及前缀和数组如何更新），例如题目1534.统计好三元组。

因为$l$和$r$都是计算出来的，因此要注意$l-1$有可能是负数，且可能会出现$l>r$的情况，还可能出现下标l和r大于题目限制下标1000的情况。

1.3 相关习题

1534.统计好三元组

2 滑动窗口与双指针

2.1 每次写题的小tip

$\bigstar$看见“连续“的东西则想到滑动窗口。

$\bigstar$可以这么说，滑动窗口替代了两次for循环，即减小了时间复杂度；如1297. 子串的最大出现次数$(LeetCode-Practice-20250729)$。

2.2 基础知识

2.1.1定长滑动窗口

先由一个题1456.定长子串中元音的最大数目来讲滑动窗口：

一开始想到的方法就是2个for循环来枚举长度为$k$的字符串判断里面有几个元音字符，但是s.length()最大值为$10^5$，$k$也是，因此不能枚举。那怎么办呢？

看题解说用滑动窗口，这是我第一次学滑动窗口。怎么把滑动窗口用在上面呢？如示例$1$，$s = “abciiidef”$，假如我们已经计算出了子串 $abc$ 的元音个数，那么从子串 $abc$ 到子串$ bci$，只需要考虑移除（离开窗口）的字母 $a$ 是不是元音，以及添加（进入窗口）的字母 $i$ 是不是元音即可，因为中间的字母 b 和 c 都在这两个子串中。

图解的表示可以参考灵茶山艾府的滑动窗口和双指针刷题专题

这就是滑动窗口的方法。我想了想，代码写为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxVowels(string s, int k) {
        int num=0;
        int ans=0;
        string x="aeiou";
        for(int i=0;i<s.length();i++){
            if(x.find(s[i])!=string::npos)num++;
            if(i==k-1)ans=num;
            if(i<k)continue;
            if(x.find(s[i-k])!=string::npos)num--;
            ans=max(ans,num);
        }
        return ans;
    }
};

完全可以把以上代码当作滑动窗口的模板！

2.1.2 逆向思维使用定向窗口

可以具体看1423. 可获得的最大点数这题，在leet-practice-0727里面有详细写逆向思维使用定向窗口的思路。

2.1.3 循环定长滑动窗口

参考1652. 拆炸弹这题的灵茶山艾府的循环定长滑动窗口的思想，for循环的条件要重新设计，以及for循环的代码块页要重新设计，即$sum$加啥涉及下标$index$取余mod的思想，$sum$减啥还是和原来一样。你写一下1652. 拆炸弹就会用了！

基础代码：

1
2
3
4
5
6
7
8
int n=code.size();
vector<int>ans(n,0);
int sum=reduce(code.begin(),code.begin()+k); // ans[0]
for(int i=0;i<n;i++){
	ans[i]=sum;
	sum+=code[(i+k) % k]-code[i];
}
return ans;

1652. 拆炸弹不只是用到了基础代码，还要再脑子转弯一下！加油！

还可以用枚举模拟写1652这一题，只是复杂度高，但是模拟用了循环的思想，还是要学习一下的！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> decrypt(vector<int>& code, int k) {
        int len = code.size();
        vector<int> ans(len);
        if(k > 0) {
            for(int i = 0;i < len;++i) {
                for(int j = 1;j <= k; ++j) {
                    ans[i] += code[(i + j) % len];
                }
            }
        }
        else if(k < 0) {
            for(int i = 0;i < len;++i) {
                for(int j = 1;j <= -k;++j) {
                    ans[i] += code[(i - j + len) % len];
                }
            }
        }
        return ans;
    }
};

特别是code数组的下标(i+j)%len与(i-j+len)%len和枚举发for循环的思想要学习一下！

除了1652. 拆炸弹，也练习一下2134. 最少交换次数来组合所有的 1 II，也是循环定长滑动窗口的题，用于巩固我们学到的循环定长滑动窗口的知识。

2.2 相关习题

1456.定长子串中元音的最大数目

2379. 得到 K 个黑块的最少涂色次数

1423. 可获得的最大点数

1052. 爱生气的书店老板比简单题多了一点点条件

1652. 拆炸弹

2134. 最少交换次数来组合所有的 1 II

1297. 子串的最大出现次数

2653. 滑动子数组的美丽值

排序

计数排序

小注意点

$\bigstar$适用于值域很小的数组的排序。

基础知识

把数组里所有数的数量都存储在map中。若此数组的值域是$[-50,50]$，先计算数组中$-50$有多少个，$-49$有多少个，以此类推，把每个数对应的数量存储在vector中。那么就有人问了，下标为负数，怎么可以存储在vector中呢？那就存储下标为“数$+n$”，而$n=(50-(-50))/2=100/2=50$。当然vector的范围要设置为$0$到$100$。

然后for循环枚举$-50$到$50$。如计数排序求第$x$小的数，设第$x$小的数为$num$，那么$<num$的数有$<x$个，$≤num$的数有$\geq x$个，就说明$num$是第$x$小的数。比如$[−1,−1,−1]$中，第$1,2,3$小的数都是$−1$。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
//先记录数组中值为-50到50的每个数的数量，存储在vector数组中
vector<int>num(101,0);
//计算数量的代码省略
//枚举
int sum=0;
for(int i=-50;i<=50;i++){
    sum+=num[i+50];
    if(sum>=x){
        //这个时候i就是第x小的数啦
        cout<<i<<endl;
        break;
    }
}

涉及的题

2653. 滑动子数组的美丽值