Massive Algorithms: LintCode

http://cherylintcode.blogspot.com/2015/07/submatrix-sum.html

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)]

http://blog.csdn.net/gqk289/article/details/69809685

这道题和求数组中哪些元素和为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]

然后用一条竖线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;
}

https://segmentfault.com/a/1190000004878083

先对矩阵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.

http://www.jiuzhang.com/solutions/submatrix-sum/

    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

LintCode - Submatrix Sum

Labels

Popular Posts