题目大意：
元素和为目标值的子矩阵数量
给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。
子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。
如果 (x1, y1, x2, y2) 和 (x1′, y1′, x2′, y2′) 两个子矩阵中部分坐标不同（如：x1 != x1’），那么这两个子矩阵也不同。
示例 1：
输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0 输出：4 解释：四个只含 0 的 1x1 子矩阵。
示例 2：
输入：matrix = [[1,-1],[-1,1]], target = 0 输出：5 解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。
提示：
1 <= matrix.length <= 300
1 <= matrix[0].length <= 300
-1000 <= matrix[i] <= 1000
-10^8 <= target <= 10^8
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1074
解题思路分析：
虽然这是一道Hard难度的题目，但之前如果做过 LeetCode 560 Subarray Sum Equals K 的话，应该会有一些灵感，本题是 Subarray Sum Equals K 的2D升级版，如果对本题没有思路，我强烈建议大家先看下之前的文章，LEETCODE 560. Subarray Sum Equals K 解题思路分析 。
本题也需要使用到presum思路来解题，只不过这个前缀和presum的计算对象是二维数组。对于任意一个点，presum[i][j]代表了从Matrix[0][0]到Matrix[i][j]之间的和。
有了前缀和之后，我们可以将二维数组拆解为多个一维数组，再用一维数组的思路去解题。
拆分数组时可以以列拆分，也可以以行拆，无论如何都可以达到遍历所有子矩阵的效果。本题以列拆分为例，对于任意两列col1和col2，我们可以得到所有行的前缀和
for(int row = 0; row < matrix.length; row++){
// 计算每一行matrix[0][col1]到matrix[row][col2]间的和
int sum_row = presum[row][col2] - presum[row][col1 - 1];
}这样，二维数组就转化为了一维数组。接下来只要遍历所有列的组合即可。
for(int col1 = 0; col1 < matrix[0].length; col1++) {
for(int col2 = col1; col2 < matrix[0].length; col2++) {
...
}
}本题解法时间复杂度为n的3次方。看下完整代码：
public int numSubmatrixSumTarget(int[][] matrix, int target) {
int rowLength = matrix.length, colLength=matrix[0].length;
int[][] presum = new int[rowLength][colLength]; // 计算前缀和
int res=0; // 返回结果
for(int row=0;row<rowLength;row++){
int rowSum=0;
for(int col=0;col<colLength;col++){
rowSum+=matrix[row][col];
presum[row][col] = rowSum + (row>0 ? presum[row-1][col] : 0);
}
}
for(int c1 = 0; c1 < colLength; c1++){ // 循环起始列
for(int c2 = c1; c2 < colLength; c2++){ // 循环终点列
Map<Integer, Integer> map = new HashMap<>(); // 用于记录前缀和个数
for(int r=0;r<rowLength;r++){ // 循环每一行
// Matrix[0][c1]到Matrix[r][c2]见的和
int sum = presum[r][c2]-(c1 > 0 ? presum[r][c1-1] : 0);
if(sum == target){ // sum等于target，结果加一
res++;
}
if(map.containsKey(sum - target)){ // map中存在sum - target
res+=map.get(sum - target); // 将个数加入到结果
}
int count = map.getOrDefault(sum, 0);
map.put(sum, count+1); // 更新当前sum的个数
}
}
}
return res;
}本解法用时839 ms。
Runtime: 839 ms, faster than 62.33% of Java online submissions for Number of Submatrices That Sum to Target.
Memory Usage: 52.5 MB, less than 100.00% of Java online submissions for Number of Submatrices That Sum to Target.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1074-number-of-submatrices-that-sum-to-target解题思路分析/