剑指Offer|LCR 013. 二维区域和检索

剑指Offer|LCR 013. 二维区域和检索 - 矩阵不可变

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

给定一个二维矩阵 matrix，以下类型的多个请求：

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

实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。

示例 1：

输入: 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出: 
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[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]]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-105 <= matrix[i][j] <= 105
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用 104 次 sumRegion 方法

法1：暴力

**分析：**两层for循环遍历

时间复杂度： $O(n^2)$

空间复杂度： $O (1)$

 var NumMatrix = function(matrix) {
   this.matrix = matrix;
};

NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    matrix = this.matrix;
    let result = 0;
    for (let r = row1; r <= row2; r++) {
        for (let c = col1; c <= col2; c++) {
            result += matrix[r][c];
        }
    }
    return result
};

const 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]
];
var obj = new NumMatrix(matrix);
console.log(obj.sumRegion(2, 1, 4, 3)); // 输出 8
console.log(obj.sumRegion(1, 1, 2, 2)); // 输出 11
console.log(obj.sumRegion(1, 2, 2, 4)); // 输出 12

leetcode上通过不了

法2：前缀和（Prefix Sum）

分析：

定义一个prefixSum ，比原本的matrix多一行多一列。

在 prefixSum 中，prefixSum[i][j] 表示从 (0,0) 到 (i-1, j-1) 的区域和。

比如要计算prefixSum[3][3]，也就是matrix[3][3]左上角的和。

在这里插入图片描述

28怎么来，要求matrix[3][3]左上角的和，也就是要求

28 = matrix[i - 1][j - 1]      //这个就是matrix[2][2]=1
+ this.prefixSum[i - 1][j]     //prefixSum[2][3]=matrix[2][3]左上角的和=16
+ this.prefixSum[i][j - 1] 	   //prefixSum[3][2]=matrix[3][2]左上角的和=22
- this.prefixSum[i - 1][j - 1];//prefixSum[2][2]=matrix[2][2]左上角的和=11
// 1+16+22-11=28

在这里插入图片描述

可以看出prefixSum[3][2]和prefixSum[2][3]有交集prefixSum[2][2],多以最后要减去一个prefixSum[2][2]，再加上maxtrix[2][2](图中绿色填充)的。

int sumRegion(int row1, int col1, int row2, int col2)

再看比如说计算sumRegion(1,1,2,2)

this.prefixSum[row2 + 1][col2 + 1] -  // prefixSum[3][3]
this.prefixSum[row1][col2 + 1] -      // prefixSum[1][3]
this.prefixSum[row2 + 1][col1] +      // prefixSum[3][1] 
this.prefixSum[row1][col1];           // prefixSum[1][1]

在这里插入图片描述

时间复杂度： $O (n)$

空间复杂度： $O (1)$

 var NumMatrix = function(matrix) {
    // 初始化 NumMatrix 类的实例属性 matrix
    this.matrix = matrix;
    const m = matrix.length;
    const n = matrix[0].length;
    
    // 创建一个 m+1 x n+1 的前缀和数组 (多加一行一列是为了方便计算)
    this.prefixSum = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

    // 填充前缀和数组
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            this.prefixSum[i][j] = matrix[i - 1][j - 1] + 
                                    this.prefixSum[i - 1][j] + 
                                    this.prefixSum[i][j - 1] - 
                                    this.prefixSum[i - 1][j - 1];
        }
    }    
};


NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    // 使用前缀和公式计算区域和
    return this.prefixSum[row2 + 1][col2 + 1] - 
           this.prefixSum[row1][col2 + 1] - 
           this.prefixSum[row2 + 1][col1] + 
           this.prefixSum[row1][col1];
};