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

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

给出矩阵 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 <= matrix.length <= 100
• 1 <= matrix[0].length <= 100
• -1000 <= matrix[i] <= 1000
• -10^8 <= target <= 10^8

方法一：前缀和

我们枚举 子矩阵的上下边界，并计算该边界内每列元素的和，则原问题转换为：

给定一个整数数组和一个整数 target，计算该数组中子数组和等于 target 的子数组个数。

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int ret = 0;
        for(int i = 0; i < m; i++){ // 枚举上边界
            int[] nums = new int[n];
            for(int j = i; j < m; j++){ //枚举下边界
                for(int c = 0; c < n; c++){
                    nums[c] += matrix[j][c]; //逐行增加 nums 数组，避免重复计算
                }
                ret += subArraySum(nums, target);
            }
        }
        return ret;
    }

    //计算子数组和等于 target 的子数组个数
    public int subArraySum(int[] nums, int target){
        //key 为子数组和，value 为子数组个数
        Map<Integer, Integer> map = new HashMap<>();
        //初始化一个子数组和为 0 ，个数为 1
        map.put(0, 1);
        // ret 为返回结果，cur 为前缀和变量
        int ret = 0, cur = 0;
        for(int num : nums){
            cur += num;
            //判断是否存在一个子数组加上 target 等于当前前缀和 cur，子数组的个数就是 子数组和为target的子数组个数
            if(map.containsKey(cur - target)){
                ret += map.get(cur - target);
            }
            map.put(cur, map.getOrDefault(cur, 0) + 1);
        }
        return ret;
    }
}

• 时间复杂度：O(M^2*n)，其中 m 和 n 分别是矩阵 matrix 的行数和列数。

• 空间复杂度：O(n)。