Submatrix Sum(Hard)和为零的子矩阵
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.
给定一个整数矩阵，请找出一个子矩阵，使得其数字之和等于0.输出答案时，请返回左上数字和右下数字的坐标。
Example
Given matrix
[
[1 ,5 ,7],
[3 ,7 ,-8],
[4 ,-8 ,9],
]
return [(1,1), (2,2)]
Challenge
O(n3) time.
public class Solution {
public int[][] submatrixSum(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] sum = new int[m+1][n+1];
int[][] res = new int[2][2];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sum[i+1][j+1] = matrix[i][j] + sum[i][j+1] + sum[i+1][j] - sum[i][j];
}
}
for (int i1 = 0; i1 < m; i1++) {
for (int i2 = i1+1; i2 <= m; i2++) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int j = 0; j <= n; j++) {
int diff = sum[i2][j] - sum[i1][j];
if (map.containsKey(diff)) {
res[0][0] = i1; res[0][1] = map.get(diff);
res[1][0] = i2-1; res[1][1] = j-1;
return res;
}
else map.put(diff, j);
}
}
}
return res;
}
}