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

一时失言乱红尘 2022-10-23 15:30 126阅读 0赞

##### 题目描述 #####

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。

##### 示例: #####

给定 matrix = [
      [3, 0, 1, 4, 2],
      [5, 6, 3, 2, 1],
      [1, 2, 0, 1, 5],
      [4, 1, 0, 1, 7],
      [1, 0, 3, 0, 5]
    ]
    
    sumRegion(2, 1, 4, 3) -> 8
    sumRegion(1, 1, 2, 2) -> 11
    sumRegion(1, 2, 2, 4) -> 12

##### 解题思路 #####

1.  这题思路与[303. 区域和检索 - 数组不可变][303. _ -]类似。
2.  同样在NumMatrix中创建一个二维数组用来存储每行的总值，即sums\[i\]\[j + 1\]为第i行，第j列的值。
3.  然后在sumRegion中循环row1到row2行，而每行的总和则为sums\[row\]\[col2 + 1\] - sums\[row\]\[col1\]。（row为某行）
4.  最后sum即为总和。

/** * @param {number[][]} matrix */
    var NumMatrix = function(matrix) { 
        const m = matrix.length
        if(m > 0) { 
            n = matrix[0].length
        }
        this.sums = new Array(m).fill(0).map(() => new Array(n + 1).fill(0))
        for(let i = 0; i < m; i ++) { 
            for(let j = 0; j < n; j ++) { 
                this.sums[i][j + 1] += this.sums[i][j] + matrix[i][j]
            }
        }
    };
    
    /** * @param {number} row1 * @param {number} col1 * @param {number} row2 * @param {number} col2 * @return {number} */
    NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) { 
        let sum = 0
        for(let i = row1; i <= row2; i ++) { 
            sum += this.sums[i][col2 + 1] - this.sums[i][col1]
        }
        return sum
    };
    
    /** * Your NumMatrix object will be instantiated and called as such: * var obj = new NumMatrix(matrix) * var param_1 = obj.sumRegion(row1,col1,row2,col2) */

[303. _ -]: https://blog.csdn.net/csdn9_14/article/details/114259749