晨哥Leetcode 1074. Number of Submatrices That Sum to Target

Given a matrix, and a target, return the number of non-empty submatrices that sum to target.

A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.

Two submatrices (x1, y1, x2, y2) and (x1’, y1’, x2’, y2’) are different if they have some coordinate that is different: for example, if x1 != x1’.

Example 1:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0

Output: 4

Explanation: The four 1x1 submatrices that only contain 0.

Example 2:

Input: matrix = [[1,-1],[-1,1]], target = 0

Output: 5

Explanation: The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.

解析：

在做这道题之前，对一维的同类subarray, prefix sum题应该要比较熟练了，如果一维的已经搞懂，二维思路是一样的

只是加上了对 列的枚举：

总共有0 … n-1个列，枚举两个列的区间i, j（可以是同一个列， i<=j）

我们可以通过提前计算，得到每一行的prefix sum， 很容易得到每一行在i …j之间的数的和

这个时候我们把列压缩成一个数了，从上往下一行一行看，这又变成了一维的subarray sum==target的题，记录之前出现sum的个数，符合条件时加上就可以了

一维的复杂度是o(n)，二维的题目，复杂度是O(n2m)，有点高，没想到最优解也就是这样了，要敢想啊

public int numSubmatrixSumTarget(int[][] d, int target) {
        if(d.length == 0 || d[0].length == 0) return 0;
        int m = d.length, n = d[0].length, res = 0;
        int[][] sum = new int[m][n+1];
        for(int k = 0; k < m; k++) {
            for(int i = 0; i < n; i++) {
                sum[k][i+1] = d[k][i] + sum[k][i];
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                int cur = 0;
                Map<Integer, Integer> map = new HashMap();
                map.put(0, 1);
                for(int k = 0; k < m; k++) {
                    cur += sum[k][j+1] - sum[k][i];
                    if(map.containsKey(cur - target)) {
                        res += map.get(cur - target);
                    }
                    map.put(cur, map.getOrDefault(cur, 0) + 1);
                }
            }
        }
        return res;
    }