优选算法——前缀和（1）：一维前缀和

🔥近津薪荼：
[个人主页]

🎬个人专栏：
《近津薪荼的算法日记》

《Linux操作系统及网络基础知识分享》

《c++基础知识详解》

《c语言基础知识详解》

✨

1.上期参考代码

class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector <int>ret;
int left=0;int right=0;
int hash1[26]={0};
int hash2[26]={0};
int m =p.size();
int count=0;
for(auto ch :p)
{
hash1[ch–'a']++;
}
while(right<s.size())
{
char in=s[right];
if(++hash2[in–'a']<=hash1[in–'a'])count++;
if(right–left+1>m)
{
char out=s[left++];
if(hash2[out–'a']—<=hash1[out–'a'])
count—;
}
if(count==m)
ret.push_back(left);
right++;
}
return ret;
}
};

2.本期知识点导图

3.本期要讲解的题目是

DP34前缀和

要点：

说白了，就是快速，多次，求给定区间的元素和，

我们有前缀和算法来专门解决这类问题。

4.解题

4.1 暴力解法：

直接遍历给定区间求和，然后返回时间复杂度为O(m*N)，m的值可达10⁵，数组长度也是10⁵，相乘得10¹⁰，不管用什么语言，写出来时间复杂度达到10¹⁰，必然超时！

4.2优解

暴力解法不够快，我们用前缀和算法，快速求得区间元素的和

前缀和的实质：

提前计算数组的累积和，将多次区间和查询的时间复杂度从 O (n) 优化到 O (1)

两步走：

1. 预处理：创建出一个前缀和数组

• 第一步：创建两个数组dp[n+1],和arr[n+1]，arr输入要处理的数组，dp[i]表示arr数组中前i个元素之和。
• 将给定数组从下标1开始输入数组arr[n+1]

为什么要创建n+1大小的数组，不应该是n吗，为什么从小标1开始？

因为第0个位置要放置元素0，方便第二步操作

• 第二步：使用公式：dp[ i ]=dp[ i-1 ]+arr[ i ]配置前缀和数组。

为了避免dp[ i-1 ]越界访问，我们才从下标1开始操作

上述创建前缀和数组的操作，时间复杂度为O(N)

2. 使用前缀和数组

我们求区间[l,r]的元素和，可以直接用dp[r]-dp[l-1]

使用前缀和数组的操作时间复杂度是O(m),也就是O(1)

使用前缀和的方法整体来看时间复杂度是O（N+m），也就是O(N)

两种方法看似时间复杂度都是O(N)，我们之前也说过，看时间复杂度，不能只从表面看表达式，于鏊看实际执行了多少条语句，一个是O(m*N)，一个是O（N+m），m的实质可达10⁵，二者根本不在一个量级~

总结一下：

代码逻辑：

• 创建两个数组
• 构建前缀和数组
• 使用前缀和数组

5.下期要讲解的题目是：

二维前缀和

6.嗟食

如果小编写的内容对佬有帮助，还请大佬点点三连加关注哦 佬的支持就是我前进的最大动力~

佬们，期待我们的下次相遇！