题目描述（中等难度）

给定矩阵的左上角坐标和右下角坐标，返回矩阵内的数字累计的和。

解法一

和 上一道题 其实差不多，上一个题是一维空间的累计，这个是二维，没做过上一题，可以先看一下，这里用同样的思路了。

如果我们只看矩阵的某一行，那其实就变成上一题了。所以我们可以提前把每一行各自的累和求出来，然后求整个矩阵的累和的时候，一行一行求即可。

/**
 * @param {number[][]} matrix
 */
var NumMatrix = function (matrix) {
    this.rowsAccumulate = [];
    let rows = matrix.length;
    if(rows === 0){
        return;
    }
    let cols = matrix[0].length;
    for (let i = 0; i < rows; i++) {
        let row = [0];
        let sum = 0;
        for (let j = 0; j < cols; j++) {
            sum += matrix[i][j];
            row.push(sum);
        }
        this.rowsAccumulate.push(row);
    }
};

/**
 * @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 = sum + this.rowsAccumulate[i][col2 + 1] - this.rowsAccumulate[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)
 */

解法二

当然，我们也可以忘记上一道题的解法，重新分析，但思想还是上一题的思想。

我们可以用 matrixAccumulate[i][j] 来保存从 (0, 0) 到 (i - 1, j - 1) 矩阵内所有数累计的和。

matrixAccumulate[0][*] 和 matrixAccumulate[*][0] 都置为 0 ，这样做的好处就是为了统一处理边界的情况，看完下边的解法，可以回过头来思考。

然后和上一道题一样，对于 (row1, col1) 和 (row2, col2) 这两个点组成的矩阵内数字的累计和可以表示为下边的式子。

this.matrixAccumulate[row2 + 1][col2 + 1] -
    this.matrixAccumulate[row1][col2 + 1] -
    this.matrixAccumulate[row2 + 1][col1] +
    this.matrixAccumulate[row1][col1]

至于为什么这样，可以结合下边的图。

我们要求的是橙色部分的矩阵。只需要用 (0, 0) 到 (row2, col2) 的矩阵，减去 (0, 0) 到 (row1, col2) 的矩阵，再减去 (0, 0) 到 (row2, col1) 的矩阵，最后加上 (0, 0) 到 (row1, col1) 的矩阵。因为 (0, 0) 到 (row1, col1) 的矩阵多减了一次。

然后可以看看坐标的分布，就可以得出上边的式子了。

之所以出现，row2 + 1 、co2 + 1 这种坐标，是因为我们的 matrixAccumulate[i][j] 来保存从 (0, 0) 到 (i - 1, j - 1) ，有一个减 1 的操作。

至于 matrixAccumulate 怎么求，我们可以使用上边类似的方法，通过矩阵的加减实现。

O 到 A 的累加，就等于 A 位置的值加上 O 的 C 的累加，加上 O 的 B 的累加，减去 O 到 D 的累加。代码的话，就是下边的样子。

this.matrixAccumulate[i][j] =
        matrix[i-1][j-1] +
        this.matrixAccumulate[i - 1][j] +
        this.matrixAccumulate[i][j - 1] -
        this.matrixAccumulate[i - 1][j - 1];
    }

总代码就是下边的了。

/**
 * @param {number[][]} matrix
 */
var NumMatrix = function (matrix) {
  this.matrixAccumulate = [];
  let rows = matrix.length;
  if (rows === 0) {
    return;
  }
  let cols = matrix[0].length;

  for (let i = 0; i <= rows; i++) {
    let row = [];
    for (let j = 0; j <= cols; j++) {
      row.push(0);
    }
    this.matrixAccumulate.push(row);
  }
  for (let i = 1; i <= rows; i++) {
    for (let j = 1; j <= cols; j++) {
      this.matrixAccumulate[i][j] =
        matrix[i-1][j-1] +
        this.matrixAccumulate[i - 1][j] +
        this.matrixAccumulate[i][j - 1] -
        this.matrixAccumulate[i - 1][j - 1];
    }
  }
};

/**
 * @param {number} row1
 * @param {number} col1
 * @param {number} row2
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {
  return (
    this.matrixAccumulate[row2 + 1][col2 + 1] -
    this.matrixAccumulate[row1][col2 + 1] -
    this.matrixAccumulate[row2 + 1][col1] +
    this.matrixAccumulate[row1][col1]
  );
};

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

再分享 StefanPochmann 大神的一个思路，上边我们用 matrixAccumulate[i][j] 来保存从 (0, 0) 到 (i - 1, j - 1) 矩阵内所有数累计的和，多了减一。虽然这种思路经常用到，就像字符串截取函数一样，一般都是包括左端点，不包括右端点，但看起来比较绕。

我们可以用 matrixAccumulate[i][j] 来保存从 (0, 0) 到 (i, j) 矩阵内所有数累计的和，这样的话，为了避免单独判断边界情况的麻烦，我们可以封装一个函数，对于下标小于 0 的边界情况直接返回 0 ，参考下边的代码。

/**
 * @param {number[][]} matrix
 */
var NumMatrix = function (matrix) {
  this.matrixAccumulate = matrix;
  let rows = matrix.length;
  if (rows === 0) {
    return;
  }
  let cols = matrix[0].length;

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      this.matrixAccumulate[i][j] +=
        this.f(i - 1, j) + this.f(i, j - 1) - this.f(i - 1, j - 1);
    }
  }
};

/**
 * @param {number} row1
 * @param {number} col1
 * @param {number} row2
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {
  return (
    this.f(row2, col2) -
    this.f(row1 - 1, col2) -
    this.f(row2, col1 - 1) +
    this.f(row1 - 1, col1 - 1)
  );
};

NumMatrix.prototype.f = function (i, j) {
  return i >= 0 && j >= 0 ? this.matrixAccumulate[i][j] : 0;
};

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

总

比较简单的一道题，基本上还是上一题的思路，想起来小学求矩形面积了，哈哈。解法二的话两种技巧都是处理边界情况的方法，将边界的逻辑和其他部分的逻辑统一了起来，前一种扩充 0 的技巧比较常用。