问题描述
来源：LeetCode第1074题
难度：困难
给出矩阵matrix和目标值target，返回元素总和等于目标值的非空子矩阵的数量。
示例 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 子矩阵。
示例 3：
输入：matrix = [[904]], target = 0
输出：0
提示：
1 <= matrix.length <= 100
1 <= matrix[0].length <= 100
-1000 <= matrix[i] <= 1000
-10^8 <= target <= 10^8
问题分析
这题是让求和等于target的子矩阵个数，如果想求子矩阵中所有元素的和，我们需要知道子矩阵的左上角以及右下角坐标，在二维数组中这个复杂度是相当高的，不能接受。那么有一种解决方式就是拉风箱，我们需要确定子矩阵的上下左三个边界，然后来移动右边界，把它转化为一维数组，如下图所示
如上图所示，这个子区间我们只需要使用一个一维数组来保存他的值，就是在子区间中同一列的进行累加，来看下代码
public int numSubmatrixSumTarget(int[][] matrix, int target) {
int count = 0;
int m = matrix.length;// 行
int n = matrix[0].length;// 列
for (int i = 0; i < m; i++) { // 枚举子区间的上边界
// sum 记录子区间的值，比如 sum[0]表示子区间中第一列的
// 元素和，他是从子区间的上边界累加到子区间的下边界
int[] sum = new int[n];
for (int j = i; j < m; j++) { // 枚举子区间的下边界
// 更新sum，他是上下累加的，每个元素的值是从上边界累加到下边界
for (int k = 0; k < n; k++)
sum[k] += matrix[j][k];
// 累加和为target的子矩阵数量
count += subarraySum(sum, target);
}
}
return count;
}
上面代码中函数subarraySum(sum, target)就是和为 K 的子数组中的代码。
联系客服
