leetcode 1074. Number of Submatrices That Sum to Target（和为target的子矩阵个数）

题目中让找出有多少个子矩阵，其元素的和为target.
子矩阵的范围：x1 <= x <= x2, y1 <= y <= y2
4个边界有任一个不同，都算不同的子矩阵。

思路：

有一种简单粗暴的方法，就是遍历所有的x1, x2, y1, y2,
用积分矩阵求和。

public int numSubmatrixSumTarget(int[][] matrix, int target) {
    
    int m = matrix.length;
    int n = matrix[0].length;
    
    // aux[i][j] is the sum of sub-matrix which start at [0][0] and end in [i][j]
    int[][] aux = new int[m + 1][n + 1]; // padding on top and left
    for (int i = 1; i < m + 1; i++) {
    
        for (int j = 1; j < n + 1; j++) {
    
            aux[i][j] = matrix[i - 1][j - 1] + aux[i - 1][j] + aux[i][j - 1] - aux[i - 1][j - 1]; 
        }
    }
    
    int res = 0;
    // try each sub-matrix
    for (int x1 = 1; x1 < m + 1; x1++) {
    
        for (int y1 = 1; y1 < n + 1; y1++) {
    
            for (int x2 = x1; x2 < m + 1; x2++) {
    
                for (int y2 = y1; y2 < n + 1; y2++) {
    
                    if (target == aux[x2][y2] - aux[x2][y1 - 1] - aux[x1 - 1][y2] + aux[x1 - 1][y1 - 1])
                        res++;
                }
            }
        }
    }
    
    return res;
}

上面的方法能通过，但是比较慢。时间上排名比较靠后。
找到了下面这种方法，

可以想象一下行的上边界是top, 下边界是bottom
然后在top~bottom这些行的范围内，一条一条（一列一列）地求和，
和保存在sum数组里，sum[col] 表示 col这一列top~bottom范围的和。

这样子矩阵的上下边界确定好了，再确定左右边界，
只需要求left ~ right范围内sum[col]的和就行了，每个sum[col]是一条，多条组合起来就是一个子矩阵。

一旦和满足==target，就算找到一个子矩阵。
遍历top : 1~m-1, bottom : top~m-1, left : 0 ~n-1, right: left ~ n-1

public int numSubmatrixSumTarget(int[][] matrix, int target) {
    
    int m = matrix.length;
    int n = matrix[0].length;
    int res = 0;
    
    // traverse upper boundary
    for (int top = 0; top < m; top++) {
    
        
        // for each upper boundary, we have a prefix sum array
        int[] sum = new int[n];
        
        // traverse lower boundary
        for (int bottom = top; bottom < m; bottom++) {
    
            
            // count the prefix sum for each column
            for (int col = 0; col < n; col++) {
    
                sum[col] += matrix[bottom][col];
            }
      
            // traverse left and right boundary
            for (int left = 0; left < n; left++) {
    
                int cnt = 0;
                for (int right = left; right < n; right++) {
    
                    cnt += sum[right];
                    if (cnt == target) res++;
                }
            }
        }
    }
    return res;
}