一、题目

给出矩阵 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’），那么这两个子矩阵也不同。

点击查看原题

二、思路

sum(matrix[0][0]，matris[i][j])指从从matrix左上角(0, 0)到右下角(i, j)区块中所有元素的和。

1）二维数组前缀和

建立dp数组，dp[i+1][j+1]代表了sum(matrix[0][0]，matris[i][j])区块的和。根据前缀和可以快速得到某一区块的值：

通过遍历数组，以各个元素为起点，不同区块大小进行遍历，构成四重循环进行求解。

2）前缀和+哈希表

先确定上边界up和下边界down，将每个sum(matrix[up][0]，matris[down-1][k])放入哈希表map中，其中k为[0, matrix[0].length)：

故而，只需要寻找map中sum(matrix[up][0]，matris[down-1][k])-target值的个数，节省了遍历时间。

三、代码

1）二维数组前缀和

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
        for (int i = 0; i < matrix.length; i++) {    // 前缀求和
            for (int j = 0; j < matrix[0].length; j++) {
                dp[i+1][j+1] = matrix[i][j] + dp[i+1][j] + dp[i][j+1] - dp[i][j];
            }
        }
        int ans = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {    // i,j是确定以matrix[i][j]为左上角起点
                for (int high = 1; high <= matrix.length - i; high++) {    // high、width分别为区块的高度和宽度
                    for (int width = 1; width <= matrix[0].length - j; width++) {
                        if (dp[i+high][j+width] - dp[i][j+width] - dp[i+high][j] + dp[i][j] == target) {
                            ans++;
                        }
                    }
                }
            }
        }
        return ans;
    }
}

matrix行和列数分别为m、n，时间复杂度为O(mn)，空间复杂度为O(mn)。

2）前缀和+哈希表

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                dp[i+1][j+1] = matrix[i][j] + dp[i+1][j] + dp[i][j+1] - dp[i][j];
            }
        }
        int ans = 0;
        for (int up = 0; up < matrix.length; up++) {
            for (int down = up+1; down <= matrix.length; down++) {
                Map<Integer, Integer> map = new HashMap();
                for (int col = 0; col < matrix[0].length; col++) {
                    int val = dp[down][col + 1]  - dp[up][col+1];
                    if (val == target) {
                        ans++;
                    }
                    ans += map.getOrDefault(val - target, 0);
                    map.put(val, map.getOrDefault(val, 0) + 1);
                }
            }
        }
        return ans;
    }
}

matrix行和列数分别为m、n，时间复杂度为O(mn)，空间复杂度为O(mn)。