前缀和:一维前缀和

数组前n项和

前缀和:从一维数组下标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);
 */
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x