前缀和的应用(leetcode 303区域和检索 - 数组不可变)超详细

2023-11-09 12:57:04

前缀和的应用(LeetCode 303区域和检索 - 数组不可变)超详细

我会从最基本的开始分析，如果不想看请直接跳转到前缀和

这里由LeetCode的一道题引入

303. 区域和检索 - 数组不可变 - 力扣（LeetCode） (leetcode-cn.com)

给定一个nums数组，实现一个NumArray类

仅有一个功能：查询nums数组中 left 到 right的和，包括left和right位置

1.最直觉的想法

我们将数组用一个类属性 num 保存起来，然后当每次查询的时候用一个for循环将数值累加起来

class NumArray {
public:
    vector<int> num;
    NumArray(vector<int>& nums) {
        /*
        	遍历nums中的元素 也可以写为 for(int i=0;i<nums.size();i++){
        		num.push_back(nums[i]);
        	}
        */
        for(int it:nums){
            num.push_back(it);
        }
    }
    int sumRange(int left, int right) {
        int sum=0;
        //将left到right上的数值累加
        for(;left<=right;left++){
            sum+=num[left];
        }
        return sum;
    }
};

这样我们在执行类的构造（初始化）时，时间复杂度是O(n)，因为我们将nums数组遍历了一遍
查询数组 left 到 right 的值时，时间复杂度是O(n)，因为我们将保存的num，从left到right遍历了一遍
空间复杂度：O(n)，因为我们将nums数组完全的保存了下来

2.提高查询速度

因为我们只需要向类外提供查询这么一个功能，所以我们并不一定要将nums完全保存

为了提高查询速度，可以用额外的空间换取查询的时间

因为查询是要查询nums[left ] [right]上的和

所以我们可以用一个二维数组在初始化的时候，先把和算好，查询的时间复杂度就变成O(1)了

class NumArray {
public:
    vector<vector<int>> num;
    NumArray(vector<int>& nums) {
        int n=nums.size();
        //这里的resize是设置num的大小/规模
        //(n,vector<int>(n))：表示由n个长度为n的vector<int>组成
        //也可以写成(n,vector<int>(n,0))，这样初始值就是0啦
        num.resize(n,vector<int>(n));
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
               for(int k=i;k<=j;k++){
                   num[i][j]+=nums[k];
               }
            }
        }
    }
    int sumRange(int left, int right) {
        return num[left][right];
    }
};

坏处就是：超时了

但这个方法其实还可以再优化一下

观察第三个循环：

算0~1的时候，我们是这样计算：num[0] [1]=nums[0]+nums[1]

算0~2的时候，我们是这样计算：num[0] [2]=nums[0]+nums[1]+nums[2]

其实，nums[0] [2]直观上就是nums数组中下标0到2的累加和，那直接拿num[0] [1]的值，加上当前的nums[2]就可以不用循环啦

nums[0] [2] = num[0] [1]+nums[2]

根据这个关系，我们可以去掉这第三个for

class NumArray {
public:
    vector<vector<int>> num;
    NumArray(vector<int>& nums) {
        int n=nums.size();
        num.resize(n,vector<int>(n));
        for(int i=0;i<n;i++){
            int sum=0;
            for(int j=i;j<n;j++){
                sum+=nums[j];
                num[i][j]=sum;
            }
        }
    }
    int sumRange(int left, int right) {
        return num[left][right];
    }
};

这回没超时，不过比一开始我们最直观的想法还慢，空间还大！

空间复杂度是：O(n²)，因为我们将所有的left到right都保存了下来

时间复杂度是：O(n²)，因为我们用了两个for循环，把值都保存下来

3.前缀和！

这里先描述一下前缀和的概念:

前缀和表示，从数组下标0开始，到当前位置所有数值的和

虽然有点啰嗦，但我还是举个栗子：3、8、16、22，就是下标0~3的前缀和

由前缀和引出的公式

我们假设前缀和就叫：preSum吧

而preSum[index]表示从0~index位置的元素和，（包括0和index位置）

当前元素的值：nums[i] = preSum[i] - preSum[i-1]

因为：

preSum[i] = nums[0] + nums[1] + nums[2] + … + nums[i-1] + nums[i]

preSum[i-1] = nums[0] + nums[1] + nums[2] + … + nums[i-1]

但是，如果i=0，即nums[0] = preSum[0] - preSum[-1]

数组下标是从0开始的，所以这里要对i=-1的时候做一个处理，直接令preSum[-1]=0即可

***或者是这样：***

那问题就简单了啊

因为求 left 到 right 的前缀和，就是求 preSum[right]-preSum[left-1]的值

这也很好理解:

当然这里也有 left = 0 , left - 1 = -1的情况，处理起来和nums[0] 一样，就不再赘述

所以怎么求preSum数组：

这还不简单，和求 2.时的第三个for循环一样

preSum[i] = preSum[i-1] + nums[i]

当前前缀和：前一个的前缀和，加上当前元素的值

class NumArray {
public:
    vector<int> preSum;
    NumArray(vector<int>& nums) {
        preSum.resize(nums.size());
        if(nums.size()==0)return;
        preSum[0]=nums[0];
        for(int i=1;i<nums.size();i++){
            preSum[i]=preSum[i-1]+nums[i];
        }
    }
    int sumRange(int left, int right) {
        if(preSum.size()==0)return 0;
        if(left==0)return preSum[right];
        else return preSum[right]-preSum[left-1];
    }
};

码农公寓