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

[力扣原题链接](https://leetcode-cn.com/problems/number-of-submatrices-that-sum-to-target/)

## 题目

给出矩阵`matrix`和目标值`target`，返回元素总和等于目标值的非空子矩阵的数量。

子矩阵`x1`,`y1`, `x2`, `y2` 是满足`x1 <= x <= x2`且`y1 <= y <= y2`的所有单元`matrix[x][y]`的集合。

如果`(x1, y1, x2, y2)`和`(x1', y1', x2', y2')`两个子矩阵中部分坐标不同`（如：x1 != x1'）`，那么这两个子矩阵也不同。

**示例 1:**

```
输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
输出：4
解释：四个只含 0 的 1x1 子矩阵。
```

**示例 2:**

```
输入：matrix = [[1,-1],[-1,1]], target = 0
输出：5
解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。

```

**示例 3:**

```
输入：matrix = [[904]], target = 0
输出：0
```

**提示：**

1. `1 <= matrix.length <= 100`
2. `1 <= matrix[0].length <= 100`
3. `-1000 <= matrix[i] <= 1000`
4. `-10^8 <= target <= 10^8`

## 思路

先求出二维数组的前缀和，再暴力遍历求出结果

## 代码

语言：Java

```
class Solution {
    /**
     * 先求出二维数组的前缀和，再暴力遍历求出结果
     * 
     * @param matrix
     * @param target
     * @return
     */
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] prefixSum = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + matrix[i-1][j-1];
            }
        }

int result = 0;
        int sum;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= i; k++) {
                    for (int l = 1; l <= j; l++) {
                       sum =  prefixSum[i][j] - prefixSum[k-1][j] - prefixSum[i][l-1] + prefixSum[k-1][l-1];
                       if(sum == target) {
                           result++;
                       }
                    }
                }
            }
        }
        return result;
    }
}
```