JZTXT

leetcode-前缀和数组&差分数组

发布时间 2023-06-26 11:51:27作者: Vege_dog

前缀和数组：

前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。（仅仅适用于原数组不变的情况，如果原数组经常修改，则需要考虑差分数组。）

 

看两道例题就清楚了：

1. 303. 区域和检索 - 数组不可变 - 力扣（LeetCode）

 由于要频繁计算某个区间内的元素之和，暴力解法复杂度太大，显然前缀和比较合适，代码如下：

class NumArray {
    //前缀和数组
    int[] sumArr;

    public NumArray(int[] nums) {
        sumArr = new int[nums.length + 1];
        for(int i = 1; i < sumArr.length; i++){
            sumArr[i] = sumArr[i - 1] + nums[i - 1];
        }
    }
    
    public int sumRange(int left, int right) {
        //计算[i, j]范围内的和是用sumArr[j + 1] - sumArr[i]计算
        return sumArr[right + 1] - sumArr[left];
    }
}

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

 

2. 304. 二维区域和检索 - 矩阵不可变 - 力扣（LeetCode）

这道题将前缀和数组扩展到了二维：

在构建前缀和数组时，可以定义前缀和数组(i, j)的值为原矩阵到由(0, 0)到(i - 1, j - 1)构成的子矩阵内部的元素之和，任意矩阵都可以由几个子矩阵的加减运算得到，原理如下图：

 代码如下：

class NumMatrix {
    int[][] sumArr;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        sumArr = new int[m + 1][n + 1];
        //初始化前缀和数组
        for(int i = 1; i < m + 1; i++){
            for(int j = 1; j < n + 1; j++){
                sumArr[i][j] = sumArr[i][j - 1] + sumArr[i - 1][j] + matrix[i - 1][j - 1] - sumArr[i - 1][j - 1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        // System.out.println("------");
        // for(int[] row : sumArr){
        //     System.out.println(Arrays.toString(row));
        // }
        return sumArr[row2 + 1][col2 + 1] - (sumArr[row2 + 1][col1] + sumArr[row1][col2 + 1] - sumArr[row1][col1]);
    }
}

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

 

 

 

class NumArray {
//前缀和数组
int[] sumArr;

public NumArray(int[] nums) {
sumArr = new int[nums.length + 1];
for(int i = 1; i < sumArr.length; i++){
sumArr[i] = sumArr[i - 1] + nums[i - 1];
}
}
 
public int sumRange(int left, int right) {
//计算[i, j]范围内的和是用sumArr[j + 1] - sumArr[i]计算
return sumArr[right + 1] - sumArr[left];
}
}

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