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)]
Challenge
O(n3) time.
这道题跟LeetCode上的那道Max Sum of Rectangle No Larger Than K很类似。
解法一：
class Solution { public: /** * @param matrix an integer matrix * @return the coordinate of the left-up and right-down number */ vector<vector<int>> submatrixSum(vector<vector<int>>& matrix) { if (matrix.empty() || matrix[0].empty()) return {}; vector<vector<int>> sums = matrix; int m = matrix.size(), n = matrix[0].size(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { int t = sums[i][j]; if (i > 0) t += sums[i - 1][j]; if (j > 0) t += sums[i][j - 1]; if (i > 0 && j > 0) t -= sums[i - 1][j - 1]; sums[i][j] = t; for (int p = 0; p <= i; ++p) { for (int q = 0; q <= j; ++q) { int d = sums[i][j]; if (p > 0) d -= sums[p - 1][j]; if (q > 0) d -= sums[i][q - 1]; if (p > 0 && q > 0) d += sums[p - 1][q - 1]; if (d == 0) return {{p, q}, {i, j}}; } } } } printVec(sums); return {}; } };
解法二：
class Solution { public: /** * @param matrix an integer matrix * @return the coordinate of the left-up and right-down number */ vector<vector<int>> submatrixSum(vector<vector<int>>& matrix) { if (matrix.empty() || matrix[0].empty()) return {}; int m = matrix.size(), n = matrix[0].size(); for (int i = 0; i < n; ++i) { vector<int> sums(m, 0); for (int j = i; j < n; ++j) { for (int k = 0; k < m; ++k) { sums[k] += matrix[k][j]; } int curSum = 0; unordered_map<int, int> map{{0,-1}}; for (int k = 0; k < m; ++k) { curSum += sums[k]; if (map.count(curSum)) return {{map[curSum] + 1, i}, {k, j}}; map[curSum] = k; } } } return {}; } };
本文转自博客园Grandyang的博客，原文链接：子矩阵之和[LintCode] Submatrix Sum ，如需转载请自行联系原博主。