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

题目链接：https://leetcode.cn/problems/range-sum-query-2d-immutable

解析：
比如要求图中红框中元素的和，可以类比求下图中红色面积：
区域4面积 = 区域5面积 - 区域2面积 - 区域3面积 + 区域1面积
因为区域1的面积被减掉了两次

所以需要根据已经给定的数组创建出一个新数组，这个数组的new_array[i][j] 代表包括matrix[i][j]在内的前i行前j列的元素和。以上面的数组为例：创建的新数组多一行和一列，方便计算。
计算方法：
new_array[i+1][j+1] = new_array[i][j+1]+new_array[i+1][j]-new_array[i][j]+matrix[i][j];

新数组（new_array）:

最后求和就是：new_array[row2+1][col2+1]-new_array[row2+1][col1]-new_array[row1][col2+1]+new_array[row1][col1]

下面是各种实现代码：

Java

class NumMatrix {
    int array[][];

    public NumMatrix(int[][] matrix) {
        int x = matrix.length;
        int y = matrix[0].length;
        array = new int[x][y];
        for(int i = 0; i<x; i++) {
            for(int j = 0; j<y; j++) {
                array[i][j] = matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for(int i = row1; i<=row2; i++){
            for(int j = col1; j<=col2; j++){
                sum += array[i][j];
            }
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Python

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        x,y = 0,0
        if matrix:
            x, y = len(matrix), len(matrix[0])
        self.presum = [[0] * (y+1) for _ in range(x+1)]
        for i in range(x):
            for j in range(y):
                self.presum[i+1][j+1] = self.presum[i][j+1] + self.presum[i+1][j] - self.presum[i][j] + matrix[i][j]
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return (self.presum[row2+1][col2+1] - self.presum[row2+1][col1] - self.presum[row1][col2+1] + self.presum[row1][col1])
1
2
3
4
5
6
7
8
9
10
11
12

C++

class NumMatrix {
public:
    vector<vector<int>> presum;

    NumMatrix(vector<vector<int>>& matrix) {
        int x = matrix.size(), y = 0;
        if(x>0){
            y = matrix[0].size();
        }
        presum.resize(x+1, vector<int>(y+1));
        for(int i = 0 ;i <x;i++){
            for(int j =0;j<y;j++) {
                presum[i+1][j+1] = presum[i][j+1]+presum[i+1][j]-presum[i][j]+matrix[i][j];
            }
        }
        
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return presum[row2+1][col2+1]-presum[row2+1][col1]-presum[row1][col2+1]+presum[row1][col1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Js

var NumMatrix = function(matrix) {
    let x=0, y = 0;
    if(matrix){
        x = matrix.length
        y = matrix[0].length
    }
    this.presum = new Array(x+1).fill(0).map(() => new Array(y+1).fill(0));
    for(let i =0; i<x; i++) {
        for(let j =0; j<y; j++) {
            this.presum[i+1][j+1] = this.presum[i][j+1] + this.presum[i+1][j] - this.presum[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) {
    return this.presum[row2+1][col2+1] - this.presum[row2+1][col1] - this.presum[row1][col2+1] + this.presum[row1][col1]
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25