【算法基础】--前缀和

一、一维前缀和

前缀和就是快速求出数组某一个连续区间内所有元素的和。

示例模板

已知一个数组arr，求前缀和

第一步，预处理一个前缀和数组dp,dp[i]表示：从[1,i]区间内所有元素和。

dp[1]=arr[1];
dp[2]=arr[1]+arr[2]=dp[1]+arr[2]
dp[3]=arr[1]+arr[2]+arr[3]=dp[2]+arr[3]
…
以此类推，可得：dp[i]=dp[i-1]+arr[i]
第二步：使用前缀和数组
假若区间【l,r】内所有元素和。可得dp[r]-dp[l-1].

相应代码：

for(int i=1;i<=n;i++)
{dp[i]=dp[i-1]+arr[i];
}

细节：下表为什么从1开始？假设求【0，3】区间和，那么dp[3]-dp[-1],dp[-1]边界直接越界了.房主边界问题。
上述代码只是个参考，具体问题应具体分析。

---

例题1：

寻找数组的中心下标

解析：

还是使用前缀和的思维。使用俩数组分别来记录中心下标左边的和，以及右边的和。 然后遍历整个数组，如果俩数组相等，返回下标i

class Solution {
public:int pivotIndex(vector<int>& nums) {int n=nums.size();vector<int>f(n),g(n);//处理前缀和 后缀和for(int i=1;i<n;i++)f[i]=f[i-1]+nums[i-1];for(int i=n-2;i>=0;i--)g[i]=g[i+1]+nums[i+1];for(int i=0;i<n;i++){if(f[i]==g[i])return i;}return -1;}
};

---

例题2：

除自身以外的数组乘积

题目描述：
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。

---

解析：这里使用的方法和上一道题解法类似，只不过换了一种说法。题目所说求除i为之外其余元素的积，我们换一种思维就是 前缀积和后缀积的积。假设我们要求i位置的值时，我们可以求出【0,i-1】位置区间所有元素积和【i+1,n-1】区间范围所有元素积。再将他俩相乘即可。草图如下：

代码：

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n=nums.size();vector<int>f(n),g(n);f[0]=g[n-1]=1;//初始化//注意这里for(int i=1;i<n;i++)f[i]=f[i-1]*nums[i-1];for(int i=n-2;i>=0;i--)g[i]=g[i+1]*nums[i+1];//使用vector<int>ans(n);for(int i=0;i<n;i++){ans[i]=g[i]*f[i];}return ans;}
};

---

例3：

和可被k整除的子数组

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。子数组 是数组中 连续 的部分。

解析：

这里先讲一下有关知识点：同余定理

在c++/java中：（负%正）=负，为了让这个余数是正数，给出了这样的方法修正：a%p+p,但是又不能确定a是正数还是负数，为了统一：(a%p+p)%p,以后取模运算，有负数时，用这个方法。

在该题中，求可被k整除的子数组个数，我们用到前缀和+哈希方法。在[0,i-1]区间内找到多少前缀和余数等于(sum%k+k)%k.,余数存进哈希表。定义个哈希表，第一个int代表前缀和的余数，第二个代表个数。

代码：

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int>hash;//存的是余数hash[0%k]=1;//余数int sum=0,res=0;for(auto x:nums){sum+=x;//算出当前位置前缀和int y=(sum%k+k)%k;//求余数if(hash.count(y))   res+=hash[y];hash[y]++;//不要忘记将余数继续扔进哈希表里}return res;}
};

---

希望读者喜欢
你们的支持是小编动力的源泉