Description

Given an integer matrix, find a submatrix where the sum of numbers is zero. Your code should return the coordinate of the left-up and right-down number.

Example

Given matrix

[
  [1 ,5 ,7],
  [3 ,7 ,-8],
  [4 ,-8 ,9],
]

return[(1,1), (2,2)]

Solution

作为Subarray Sum的follow up，首先，取一个n+1* m+1的sum数组，sum[i][j]表示(0, 0), (0, i-1), (i-1, j-1), (i-1, 0)这个4个点组成的矩形的sum。初始状态为：sum[0][j] = sum[i][0] = 0, 状态方程为sum[i][j] = matrix[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]

再找sum为0的submatrix：如果(i1, j1), (i1, j2), (i2, j2), (i2, j1) 4个点组成的子矩阵sum为0，那么sum[i2][j2] - sum[i1][j2] - sum[i2][j1] + sum[i1][j1] = 0 ==> 对任意i1和i2，横向遍历，如果存在j1, j2两个纵坐标，使得j1与i1, i2相交时的势差和j2与i1, i2相交时的势差相等，则找到符合条中间的子矩阵，这里判断势差的相等可以和subarray sum一样用hashmap解决.
注意子矩阵左上角的顶点是exclusive的，而右下角的顶点是inclusive的，因此结果中左上和右下的坐标分别为(i1, j1), (i2-1, j2-1)

public class Solution {
    /**
     * @param matrix an integer matrix
     * @return the coordinate of the left-up and right-down number
     */
    public int[][] submatrixSum(int[][] matrix) {
        // Write your code here
        int[][] ret = new int[2][2];
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] sum = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = matrix[i-1][j-1] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
            }
        }

        for (int i1 = 0; i1 < n; i1++) {
            for (int i2 = i1+1; i2 <= n; i2++) {
                HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
                for (int j = 0; j <= m; j++) {
                    int diff = sum[i2][j] - sum[i1][j];
                    if (map.containsKey(diff)) {
                        ret[0][0] = i1;
                        ret[0][1] = map.get(diff);
                        ret[1][0] = i2-1;
                        ret[1][1] = j-1;
                    } else {
                        map.put(diff, j);
                    }
                }
            }
        }

        return ret;
    }
}