1074.元素和为目标值的子矩阵数量

链接：1074.元素和为目标值的子矩阵数量
难度：Hard
标签：数组、哈希表、矩阵、前缀和
简介：给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。

题解 1 - typescript

• 编辑时间：2021-05-29
• 执行用时：500ms
• 内存消耗：42.3MB
• 编程语言：typescript
• 解法介绍：暴力循环。

function numSubmatrixSumTarget(matrix: number[][], target: number): number {
  const rowLen = matrix.length;
  const colLen = matrix[0].length;
  const prefixSumList: number[][] = new Array(rowLen + 1)
    .fill(0)
    .map(_ => new Array(colLen + 1).fill(0));
  for (let row = 0; row < rowLen; row++) {
    for (let col = 0; col < colLen; col++) {
      prefixSumList[row + 1][col + 1] =
        prefixSumList[row + 1][col] +
        prefixSumList[row][col + 1] -
        prefixSumList[row][col] +
        matrix[row][col];
    }
  }
  let ans = 0;
  for (let endRow = 0; endRow < rowLen; endRow++) {
    for (let endCol = 0; endCol < colLen; endCol++) {
      for (let startRow = 0; startRow <= endRow; startRow++) {
        for (let startCol = 0; startCol <= endCol; startCol++) {
          if (
            prefixSumList[endRow + 1][endCol + 1] -
              prefixSumList[endRow + 1][startCol] -
              prefixSumList[startRow][endCol + 1] +
              prefixSumList[startRow][startCol] ===
            target
          ) {
            ans++;
          }
        }
      }
    }
  }
  return ans;
}