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.

Have you met this question in a real interview?

Yes

Example

Given matrix

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

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

1. 暴力枚举的话，需要枚举行起点， 行终点， 列起点， 列终点， 如果用summatrix和的话，复杂度是O(n^4)

2. 如果利用矩阵特性，枚举行起点和终点时，在判断每一列时，列高并不会发生变化， 所以可以将各列延列合并为一个每一位记录该列所有行sum的数组，即变成了一道 subarray sum了。

要注意的是，hashmap需要针对每一个 sum列数组，需要initialization 0, -1这个位置，一遍某一段的和为0

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[][] ans = new int[2][2];
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return new int[0][0];
        }

        int[][] sum = new int[matrix.length + 1][matrix[0].length];
        for (int i = 1; i <= matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                sum[i][j] = sum[i - 1][j] + matrix[i - 1][j];
            }
        }

        //System.out.println(sum[12][0] - sum[1][0]);
        for (int i = 0; i < matrix.length; i++) {
            for (int j = i; j < matrix.length; j++) {
                HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
                hash.put(0, -1);
                int curSum = 0;
                for (int k = 0; k < matrix[0].length; k++) {
                    curSum += sum[j + 1][k] - sum[i][k];
                    if (hash.containsKey(curSum)) {
                        ans[0][0] = i;
                        ans[0][1] = hash.get(curSum) + 1;
                        ans[1][0] = j;
                        ans[1][1] = k;
                        System.out.println(curSum);
                        System.out.println(i);
                        System.out.println(j);
                        System.out.println(k);
                        System.out.println(ans[0][0] + "," + ans[0][1]);
                        System.out.println(ans[1][0] + "," + ans[1][1]);

                        return ans;
                    }
                    hash.put(curSum, k);
                }
            }
        }

        return ans;

    }
}