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

链接：304.二维区域和检索-矩阵不可变
难度：Medium
标签：设计、数组、矩阵、前缀和
简介：给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

题解 1 - typescript

• 编辑时间：2021-03-02
• 执行用时：120ms
• 内存消耗：42.9MB
• 编程语言：typescript
• 解法介绍：利用前缀和进行快速计算。

class NumMatrix {
  private sumMatrix: number[][] = [];
  constructor(matrix: number[][]) {
    const rowLen = matrix.length;
    if (rowLen === 0) return;
    const colLen = matrix[0].length;
    for (let row = 0; row < rowLen; row++) {
      const arr: number[] = [];
      for (let col = 0; col < colLen; col++) {
        const num = matrix[row][col];
        if (col === 0 && row === 0) {
          arr.push(num);
        } else if (col === 0) {
          arr.push(this.sumMatrix[row - 1][col] + num);
        } else if (row === 0) {
          arr.push(arr[col - 1] + num);
        } else {
          arr.push(
            this.sumMatrix[row - 1][col] + arr[col - 1] + num - this.sumMatrix[row - 1][col - 1]
          );
        }
      }
      this.sumMatrix.push(arr);
    }
  }
  sumRegion(row1: number, col1: number, row2: number, col2: number): number {
    return (
      this.sumMatrix[row2][col2] -
      (col1 > 0 ? this.sumMatrix[row2][col1 - 1] : 0) -
      (row1 > 0 ? this.sumMatrix[row1 - 1][col2] : 0) +
      (row1 > 0 && col1 > 0 ? this.sumMatrix[row1 - 1][col1 - 1] : 0)
    );
  }
}