20210302 LeetCode 每日一题，冲！｜刷题打卡

题目描述

Leetcode 链接：304 二维区域和检索 - 矩阵不可变（medium）

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (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

提示：

• 你可以假设矩阵不可变。
• 会多次调用 sumRegion 方法。
• 你可以假设 row1 ≤ row2 且 col1 ≤ col2 。

JavaScript 模板：

/**
 * @param {number[][]} matrix
 */
var NumMatrix = function(matrix) {

};

/** 
 * @param {number} row1 
 * @param {number} col1 
 * @param {number} row2 
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {

};

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

思路分析

有了昨天前缀和的经验，第一个思路就是将二维的数组中的每一行都转换成用于表示前缀和的数组：

1. 初始化一个前缀和数组，初始化的时间复杂度为 O(mn)，空间复杂度为 O(mn)，m 为行数，n 为列数：

var NumMatrix = function (matrix) {
  if (matrix == 0) { // 注意 matrix 为 [[]] 的情况！
    this.empty = true;
  }
  else {
    let x = matrix[0].length, y = matrix.length;
    this.preSumArray = []; // 建立前缀和数组
    for (let i = 0; i < y; i++) {
      let preSum = [0];
      for (let j = 0; j < x; j++) {
        preSum[j + 1] = preSum[j] + matrix[i][j];
      }
      this.preSumArray.push(preSum); // 建立并添加每一行的前缀和数组
    }
  }
};

2. 在调用 sumRange 方法时，我们遍历每一行，然后返回其中指定位置的前缀和之差即可，查询的时间复杂度为 O(m)，m 为行数：

NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {
  if (this.empty) { // 若为空数组则不返回值
    return;
  }
  let sum = 0;
  for (let i = row1; i < row2 + 1; i++) { // 计算每行的前缀和之差
    sum += this.preSumArray[i][col2 + 1];
    sum -= this.preSumArray[i][col1];
  }
  return sum;
};

运气不错，一次过了：

优化一下

对于这个问题，随着二维矩阵的加入，我们查询的时间就变成了 O(m) 而非之前的 O(1)，这样的查询速度肯定不是最理想的。那么我们有什么办法来继续缩短查询时间呢？其实办法是有的，关键点还是在于初始化。

在上面的方法中，我们初始化的前缀和只是当前这行的前缀和，所以说我们在查询时才需要遍历每一行。我们可以在建立前缀和的时候就直接建立一个基于每一行以及每一列而形成的二维前缀和，这样的话在查询时，就可以以 O(1) 的时间复杂度求解了。

想象一下我们要求出蓝色部分的和时，我们只需要求出四个角所对应的二维前缀和即，然后进行一下运算就行了，即紫色部分减去橙色和红色部分，最后再加上绿色部分即可：

1. 建立二维前缀和数组，时间复杂度为 O(mn)，空间复杂度为 O(mn)，m 为行数，n 为列数：

var NumMatrix = function (matrix) {
  if (matrix == 0) {
    this.empty = true;
  }
  else {
    let x = matrix[0].length, y = matrix.length;
    this.preSumArray = new Array(y + 1).fill(0).map(() => new Array(x + 1).fill(0));
    for (let i = 0; i < y; i++) {
      for (let j = 0; j < x; j++) {
        this.preSumArray[i + 1][j + 1] = matrix[i][j] +
          this.preSumArray[i][j + 1] +
          this.preSumArray[i + 1][j] -
          this.preSumArray[i][j];
      }
    }
  }
};

不过在查询时，时间复杂度就降为了 O(1)：

NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {
  if (this.empty) {
    return;
  }
  return this.preSumArray[row1][col1] +
    this.preSumArray[row2 + 1][col2 + 1] -
    this.preSumArray[row2 + 1][col1] -
    this.preSumArray[row1][col2 + 1]
};

提交一下：

总结一下

通过在初始化时建立二维前缀和而非单行的前缀和，我们成功的将查询的时间复杂度从 O(m) 降到了 O(1)，从而得到的更为高效的解法。

小伙伴们一起来用 JavaScript 刷算法吧：LeetCode-JavaScript