[一维前缀和]leetcode303：区域和检索 - 数组不可变(easy)_leetcode 一维前缀和

题目：

题解：

• 一维前缀和，元素数组[0,j]的前缀和对应prefix[j+1]

代码如下：

class NumArray {
private:
    vector<int> prefix;
public:
    //题解：一维前缀和
    NumArray(vector<int>& nums) {
        int n=nums.size();
        prefix.resize(n+1,0);
        for(int i=1;i<=n;++i){
            prefix[i]=prefix[i-1]+nums[i-1];
        }
    }
    //元素数组[0,j]的前缀和对应prefix[j+1],原始数组[0,i]的前缀和对应prefix[i+1]，而[i,j]的前缀和需要包含下标为i的元素
    //所以要减去prefix[i]，因为prfix表示的前缀和为[0,i-1]的
    int sumRange(int i, int j) {
        return prefix[j+1]-prefix[i];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18