算法技巧：前缀和数组刷题合集

303. 区域和检索 - 数组不可变

题目要求你实现这样一个类：

class NumArray {

    public NumArray(int[] nums) {}

    /* 查询闭区间 [left, right] 的累加和 */
    public int sumRange(int left, int right) {}
}   

sumRange函数需要计算并返回一个索引区间之内的元素和，没学过前缀和的人可能写出如下代码：

class NumArray {

    private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
    }

    public int sumRange(int left, int right) {
        int res = 0;
        for (int i = left; i <= right; i++) {
            res += nums[i];
        }
        return res;
    }
}  

这样，可以达到效果，但是效率很差，因为sumRange方法会被频繁调用，而它的时间复杂度是O(N)，其中N代表nums数组的长度。

这道题的最优解法是使用前缀和技巧，将sumRange函数的时间复杂度降为O(1)，说白了就是不要在sumRange里面用 for 循环，咋整？

代码实现：

/**
 * @param {number[]} nums
 */
var NumArray = function(nums) {
    let presum=[];
    presum[0]=0;
    for(let i=1;i<nums.length+1;i++){
        presum[i]=presum[i-1]+nums[i-1];
    }
    this.preSum=presum;

};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function(left, right) {
    return this.preSum[right+1]-this.preSum[left]
};

/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * var param_1 = obj.sumRange(left,right)
 */

如果我想求索引区间[1, 4]内的所有元素之和，就可以通过preSum[5] - preSum[1]得出。

这样，sumRange函数仅仅需要做一次减法运算，避免了每次进行 for 循环调用，最坏时间复杂度为常数O(1)。

304. 二维区域和检索 - 矩阵不可变

如果我想计算红色的这个子矩阵的元素之和，可以用绿色矩阵减去蓝色矩阵减去橙色矩阵最后加上粉色矩阵，而绿蓝橙粉这四个矩阵有一个共同的特点，就是左上角就是(0, 0)原点。

那么我们可以维护一个二维preSum数组，专门记录以原点为顶点的矩阵的元素之和，就可以用几次加减运算算出任何一个子矩阵的元素和：

/**
 * @param {number[][]} matrix
 */
 var NumMatrix = function(matrix) {
    let m=matrix.length;
    if(m>0){
        let n=matrix[0].length;
        this.Presum=new Array(m+1).fill(0).map(()=>new Array(n+1).fill(0));
        for(let i=1;i<m+1;i++){//计算前缀和，注意0，0要空开，方便计算
            for(let j=1;j<n+1;j++){
                this.Presum[i][j]=this.Presum[i][j-1]+this.Presum[i-1][j]-this.Presum[i-1][j-1]+matrix[i-1][j-1];
            }
        }

    }

};

/** 
 * @param {number} row1 
 * @param {number} col1 
 * @param {number} row2 
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    return this.Presum[row2+1][col2+1] - this.Presum[row1][col2+1]-this.Presum[row2+1][col1]+this.Presum[row1][col1];
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * var obj = new NumMatrix(matrix)
 * var param_1 = obj.sumRegion(row1,col1,row2,col2)
 */

https://mp.weixin.qq.com/s/EwAH3JDs5WFO6-LFmI3-2Q