题目

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (_row_1, _col_1) and lower right corner (_row_2, _col_2).
image.png
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

  1. Given matrix = [
  2.   [3, 0, 1, 4, 2],
  3.   [5, 6, 3, 2, 1],
  4.   [1, 2, 0, 1, 5],
  5.   [4, 1, 0, 1, 7],
  6.   [1, 0, 3, 0, 5]
  7. ]
  9. sumRegion(2, 1, 4, 3) -> 8
  10. sumRegion(1, 1, 2, 2) -> 11
  11. sumRegion(1, 2, 2, 4) -> 12

Note:

  1. You may assume that the matrix does not change.
  2. There are many calls to sumRegion function.
  3. You may assume that _row_1 ≤ _row_2 and _col_1 ≤ _col_2.

题意

给定一个整数矩阵，求其中一个子矩阵的数字之和。

思路

一种方法是在0303. Range Sum Query - Immutable (E)的基础上，将矩阵中每一行的sum情况缓存，求指定矩阵和时，只要累加该矩阵每一行对应的sum值即可。

更好的策略是将一维缓存的方法进行推广，进行二维缓存：
image.png
0304. Range Sum Query 2D - Immutable (M) - 图3

代码实现

Java

一维缓存

  1. class NumMatrix {
  2.     private int[][] sum;
  4.     public NumMatrix(int[][] matrix) {
  5.         if (matrix.length != 0) {
  6.             sum = new int[matrix.length][matrix[0].length + 1];
  7.             for (int i = 0; i < matrix.length; i++) {
  8.                 for (int j = 0; j < matrix[0].length; j++) {
  9.                     sum[i][j + 1] += sum[i][j] + matrix[i][j];
  10.                 }
  11.             }
  12.         }
  13.     }
  15.     public int sumRegion(int row1, int col1, int row2, int col2) {
  16.         int total = 0;
  17.         for (int i = row1; i <= row2; i++) {
  18.             total += sum[i][col2 + 1] - sum[i][col1];
  19.         }
  20.         return total;
  21.     }
  22. }

二维缓存

  1. class NumMatrix {
  2.     private int[][] sum;
  4.     public NumMatrix(int[][] matrix) {
  5.         if (matrix.length > 0) {
  6.             int m = matrix.length, n = matrix[0].length;
  7.             sum = new int[m + 1][n + 1];
  8.             for (int i = 0; i < m; i++) {
  9.                 for (int j = 0; j < n; j++) {
  10.                     sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] + matrix[i][j] - sum[i][j];
  11.                 }
  12.             }
  13.         }
  14.     }
  16.     public int sumRegion(int row1, int col1, int row2, int col2) {
  17.         return sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - sum[row1][col2 + 1] + sum[row1][col1];
  18.     }
  19. }

JavaScript

  1. /**
  2.  * @param {number[][]} matrix
  3.  */
  4. var NumMatrix = function (matrix) {
  5.   const m = matrix.length
  6.   const n = matrix[0].length
  8.   this.sumMatrix = new Array(m + 1).fill(0).map(item => [])
  10.   for (let i = 0; i < m; i++) {
  11.     let rowSum = 0;
  12.     for (let j = 0; j < n; j++) {
  13.       rowSum += matrix[i][j]
  14.       this.sumMatrix[i][j] = i === 0 ? rowSum : rowSum + this.sumMatrix[i - 1][j]
  15.     }
  16.   }
  17. }
  19. /** 
  20.  * @param {number} row1 
  21.  * @param {number} col1 
  22.  * @param {number} row2 
  23.  * @param {number} col2
  24.  * @return {number}
  25.  */
  26. NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {
  27.   const a = this.sumMatrix[row2][col2]
  28.   const b = col1 > 0 ? this.sumMatrix[row2][col1 - 1] : 0
  29.   const c = row1 > 0 ? this.sumMatrix[row1 - 1][col2] : 0
  30.   const d = row1 > 0 && col1 > 0 ? this.sumMatrix[row1 - 1][col1 - 1] : 0
  31.   return a - b - c + d
  32. }