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

标签：sumArr 前缀 nums int NumArray 差分 数组 leetcode

前缀和数组：

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

模版如下：

class PrefixSum {
    // 前缀和数组
    private int[] preSum;

    /* 输入一个数组，构造前缀和 */
    public PrefixSum(int[] nums) {
        // preSum[0] = 0，便于计算累加和
        preSum = new int[nums.length + 1];
        // 计算 nums 的累加和
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }
    
    /* 查询闭区间 [left, right] 的累加和 */
    public int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
}

 

 

看两道例题就清楚了：

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); */

标签：sumArr,前缀,nums,int,NumArray,差分,数组,leetcode
From： https://www.cnblogs.com/xkge/p/17505271.html