前缀和:从一维数组下标0开始,一直到第n项所有项的总和。
一维前缀和
一维数组的前n项和
为啥要用前缀和?
假设你要查找某个数组从第1项一直到第88项的和。那很明显,写一个for循环求和即可。
但是你现在要继续求从第2项到第89项的和,求完只会又被要求求出从第3项到第100项的和。这意味着如果你用暴力的for循环来解决这个问题,每有一次查询就要去遍历一次数组。
于是我们引入了前缀和:对数组中的每一个元素都求出“从第0项一直到该元素(包括该元素)”的和。并新建一个sum数组存放前缀和的值。
这有什么用呢?假设现在你要求从第3项到第100项的和,那么你就可以用”从第1项到第100项“的和,减去”从第1项到第2项“的和。相当于求它们的交集。
实例:区域和检索 – 数组不可变
Leetcode题目
这里将leetcode上的303题拿来作为例子。
要去求nums[left]到nums[right](包括两个元素本身)的和。如果用暴力直接写个for循环,那么后面查询次数多起来的时候就会超时。
所以要用前缀和。新建一个sum数组,用来存放前缀和的结果。
写者注
用resize对sum数组进行初始化,会同时把sum中的元素的初值设为0。如果没有初始化,由于vector的特性,在vector初始化之前你是无法通过下标的形式(sum[i])的方式访问vector的。
接下来求前缀和:
- sum[0],此时还没有元素需要相加。
- sum[1],表示从数组第1项(以下标为0为开始)的元素求和。此时sum[1]=sum[0]+nums[0]
- sum[2],求出从第1项到第2项的和。此时sum[2]=sum[1]+nums[1]。
- ….
- sum[n+1],表示从第1项到第n项的和。此时sum[n+1]=sum[n]+nums[n]
有了前缀和,那要求数组中任意区域的和也很简单了。
class NumArray {
public:
vector<int>sum;
NumArray(vector<int>& nums) {
int size=nums.size();
sum.resize(size+1);
for(int i=0;i<size;i++)
{
sum[i+1]=sum[i]+nums[i];
}
}
int sumRange(int left, int right) {
return sum[right+1]-sum[left];
}
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* int param_1 = obj->sumRange(left,right);
*/