http://cherylintcode.blogspot.com/2015/07/submatrix-sum.html
http://blog.csdn.net/gqk289/article/details/69809685
public int[][] submatrixSum(int[][] matrix) {
// Write your code here
int m = matrix.length, n = matrix[0].length;
int[][] res = new int[2][2];
for(int i = 0; i < n; i++){
int[] sum = new int[m];
for(int j = i; j < n; j++){
for(int k = 0; k < m; k++){
sum[k] += matrix[k][j];
}
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int lastSum = 0;
map.put(0, -1); // important
for(int l = 0; l < m; l++){
lastSum += sum[l];
if(map.containsKey(lastSum)){
res = new int[][] {{map.get(lastSum)+1, i}, {l, j}};
return res;
}
map.put(lastSum, l);
}
}
}
return res;
}
http://sidbai.github.io/2015/06/11/Submatrix-Sum/
http://www.1point3acres.com/bbs/thread-146423-1-1.html
Given an array, find whether it exist an subarray that sum of subarray is equal to given number
简单的说就是给一个array,和一个数字,问存在一个subarray,他的和等于那个数字。注意,subarray的意思是一个连续的元素的subarray from array。
一开始给了N^2的暴力算法,之后给了O(N)的算法,解法是用一个新的数组保存从0到当前元素的和,然后再用hash表保存下,再搜索一次即可。
上面那题的follow up,不过array变成了matrix,找的也是submatrix
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)]
这道题和求数组中哪些元素和为0的解决方法一样,只是数组中求的是前i个元素和前j个元素和相等,则i-j元素和为0,而这里只是变成2维的而已。
sum[i][j]表示matrix[0][0]到matrix[i-1][j-1]所有元素的和。
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + matrix[i][j] - sum[i - 1][j - 1]
sum[i][j]表示matrix[0][0]到matrix[i-1][j-1]所有元素的和。
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + matrix[i][j] - sum[i - 1][j - 1]
然后用一条竖线k扫描,diff表示0 ~ k && i ~ j的子矩阵的和,如果与前序某个子矩阵的和相等,则找到对应和为零的子矩阵
注意map初始化的位置
- public int[][] submatrixSum(int[][] matrix) {
- int[][] res = new int[2][2];
- if (matrix == null || matrix.length == 0) {
- return res;
- }
- int row = matrix.length;
- int col = matrix[0].length;
- int[][] sum = new int[row + 1][col + 1];
- for (int i = 0; i < row; i++) {
- for (int j = 0; j < col; j++) {
- sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] + matrix[i][j] - sum[i][j];
- }
- }
- for (int i = 0; i < row; i++) {
- for (int j = i + 1; j <= row; j++) {
- HashMap<Integer, Integer> map = new HashMap();
- for (int k = 0; k <= col; k++) {
- int diff = sum[j][k] - sum[i][k];
- if (map.containsKey(diff)) {
- res[0][0] = i;
- res[0][1] = map.get(diff);
- res[1][0] = j - 1;
- res[1][1] = k - 1;
- return res;
- } else {
- map.put(diff, k);
- }
- }
- }
- }
- return res;
- }
先对矩阵
matrix
的每个点到左顶点之间的子矩阵求和,存在新矩阵sum
上。注意,sum[i+1][j+1]
代表的是matrix[0][0]
到matrix[i][j]
的子矩阵求和。如下所示:Given matrix[m][n]
------------------
[
[1 ,5 ,7],
[3 ,7 ,-8],
[4 ,-8 ,9],
]
Get sum[m+1][n+1]
-----------------
0 0 0 0
0 1 6 13
0 4 16 15
0 8 12 20
然后,我们进行这样的操作,从0开始,确定两行
i1
、i2
,再将第k列的sum[i1][k]
和sum[i2][k]
相减,就得到matrix[i1][0]
到matrix[i2][k-1]
的子矩阵(i2-i1行,k列)求和diff
,存入map。还是在这两行,假设计算到第j列,得到了相等的和diff
。说明从i1到i2行,从k到j列的子矩阵求和为0,即相当于两个平行放置的矩形,若左边的值为diff
,左边与右边之和也是diff
,那么右边的值一定为0
。下面是map中存放操作的例子:diff-j chart
------------
diff j
1 1 i1 = 0, i2 = 1
6 2
13 3
4 1 i1 = 0, i2 = 2
16 2
15 3
8 1 i1 = 0, i2 = 3
12 2
20 3
3 1 i1 = 1, i2 = 2
10 2
2 3
------------------------------
(above res has no same pair in same region)
7 1 i1 = 1, i2 = 3
6 2
7 3 diff-j pair exists in map
res[0][0] = i1 = 1, res[0][1] = map.get(diff) = 1,
res[1][0] = i2 - 1 = 3 - 1 = 2, res[1][1] = j = 2,
so res = [(1, 1), (2, 2)]
http://techinpad.blogspot.com/2015/06/lintcode-submatrix-sum.html
If the matrix is Nx1, we can solve it easily like sum of contiguous subsequense. If it's Nx2, we just need to repeat the same process 3 times -- the first column, the second column and sum of the two columns as an Nx1 array. That's applicable to any cases.
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; }
public int[][] submatrixSum(int[][] matrix) {
// Write your code here
int m = matrix.length, n = matrix[0].length;
int[][] res = new int[2][2];
for(int i = 0; i < n; i++){
int[] sum = new int[m];
for(int j = i; j < n; j++){
for(int k = 0; k < m; k++){
sum[k] += matrix[k][j];
}
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int lastSum = 0;
map.put(0, -1); // important
for(int l = 0; l < m; l++){
lastSum += sum[l];
if(map.containsKey(lastSum)){
res = new int[][] {{map.get(lastSum)+1, i}, {l, j}};
return res;
}
map.put(lastSum, l);
}
}
}
return res;
}
http://sidbai.github.io/2015/06/11/Submatrix-Sum/
http://www.1point3acres.com/bbs/thread-146423-1-1.html
Given an array, find whether it exist an subarray that sum of subarray is equal to given number
简单的说就是给一个array,和一个数字,问存在一个subarray,他的和等于那个数字。注意,subarray的意思是一个连续的元素的subarray from array。
一开始给了N^2的暴力算法,之后给了O(N)的算法,解法是用一个新的数组保存从0到当前元素的和,然后再用hash表保存下,再搜索一次即可。
上面那题的follow up,不过array变成了matrix,找的也是submatrix