题目地址：

https://www.lintcode.com/problem/submatrix-sum/description

给定一个二维矩阵$A$，求其一个和为$0$的子矩阵，返回其左上和右下数字坐标。

如果是一维数组的话，可以先算一下前缀和，然后看一下有没有两个前缀和是相等的即可。发现相等，则两个下标之间的数字和就是$0$。对于二维矩阵，则可以枚举左上数字所在行和右下数字所在行，例如枚举了下标为$i$和$j$的两行，可以计算一下$[A[i:j,0:0],A[i:j,0:1],A[i:j,0:2],...,A[i:j,0:n-1]]$（$n$为矩阵列数，$A[i:j,k:l]$指的是从$A[i][k]$到$A[j:l]$的子矩阵的和），然后就转化为了一维的情形了。代码如下：

import java.util.HashMap; import java.util.Map; public class Solution { /* * @param matrix: an integer matrix * @return: the coordinate of the left-up and right-down number */ public int[][] submatrixSum(int[][] matrix) { // write your code here int[][] res = null; if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return res; } int m = matrix.length, n = matrix[0].length; // 算一下矩阵matrix的前缀和矩阵 int[][] preSum = new int[m + 1][n + 1]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { preSum[i + 1][j + 1] = matrix[i][j] + preSum[i + 1][j] + preSum[i][j + 1] - preSum[i][j]; } } // 枚举两行 for (int i = 0; i < m; i++) { for (int j = i; j < m; j++) { // 计算这两行对应的前缀和（具体参考上面的解释） int[] nums = new int[n + 1]; for (int k = 0; k < n; k++) { // 计算从(i, 0)到(j, k - 1)的子矩阵数字和 nums[k + 1] = preSum[j + 1][k + 1] - preSum[j + 1][0] - preSum[i][k + 1] + preSum[i][0]; } // 解一下一维情形，返回的下标是前缀和相等的两列的下标 int[] idx = solveOneD(nums); if (idx != null) { res = new int[][]{{i, idx[0] + 1}, {j, idx[1]}}; return res; } } } return res; } private int[] solveOneD(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])) { int start = map.get(nums[i]); return new int[]{start - 1, i - 1}; } map.put(nums[i], i); } return null; } }

时间复杂度$O(n^3)$，空间$O(n^2)$。