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.
If there are multiple answers, you can return any of them.
Example 1:
Input:
[
[1, 5, 7],
[3, 7, -8],
[4, -8 ,9]
]
Output: [[1, 1], [2, 2]]
Example 2:
Input:
[
[0, 1],
[1, 0]
]
Output: [[0, 0], [0, 0]]
O(n3) time.
思路：
用前缀和优化, 令 sum[i][j] = sum[0][j] + sum[1][j] + ... + sum[i][j]
然后枚举上下边界, 这样就相当于在一行内, 求一个数组连续子串和为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) {
int[][] result = new int[2][2];
int M = matrix.length;
if (M == 0) return result;
int N = matrix[0].length;
if (N == 0) return result;
// pre-compute: sum[i][j] = sum of submatrix [(0, 0), (i, j)]
int[][] sum = new int[M+1][N+1];
for (int j = 0; j <= N; ++j)
sum[0][j] = 0;
for (int i = 1; i <= M; ++i)
sum[i][0] = 0;
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
sum[i+1][j+1] = matrix[i][j] + sum[i+1][j] + sum[i][j+1] - sum[i][j];
for (int l = 0; l < M; ++l) {
for (int h = l+1; h <= M; ++h) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int j = 0; j <= N; ++j) {
int diff = sum[h][j] - sum[l][j];
if (map.containsKey(diff)) {
int k = map.get(diff);
result[0][0] = l; result[0][1] = k;
result[1][0] = h-1; result[1][1] = j-1;
return result;
} else {
map.put(diff, j);
}
}
}
}
return result;
}
}
原文：https://www.cnblogs.com/FLAGyuri/p/12078486.html