问题描述
Given a matrix and a target, return the number of non-empty submatrices that sum to target.
A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.
Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'.
Example 1:
Input: matrix = [[0,1,0],[1,1,1],[0,1,0] ], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.
Example 2:
Input: matrix = [[1,-1],[-1,1] ], target = 0
Output: 5
Explanation: The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.
Example 3:
Input: matrix = [[904] ], target = 0
Output: 0
Constraints:
- 1 <= matrix.length <= 100
- 1 <= matrix[0].length <= 100
- -1000 <= matrix[i] <= 1000
- -10^8 <= target <= 10^8
问题分析
首先，按照最朴素的想法来解决的话，我们需要针对每一个坐标点，以这个坐标为子矩阵的左上角，计算所有可能长宽组合的子矩阵和，统计所有结果和等于target的数量。
在这个过程中，我们可以看到，存在很多的重复计算；因此，我们可以先计算出每一行的prefix sums，这样在计算子矩阵和时，我们只需要对子矩阵的每一行，用 prefixsums[end] - prefixsums[start-1]就能得到 [start, end]之间元素的和；
综上，初始解法如下:
基础解法
// base solution
func numSubmatrixSumTarget(matrix [][]int, target int) int {
rows := len(matrix)
cols := len(matrix[0])
prefixsums := [][]int{}
for i := 0; i < rows; i++ {
prefixsums = append(prefixsums, make([]int, cols))
}
// 计算每一行的prefix sums
for row := 0; row < rows; row++ {
sum := 0
for col := 0; col < cols; col++ {
sum += matrix[row][col]
prefixsums[row][col] = sum
}
}
ans := 0
for row := 0; row < rows; row++ {
for col := 0; col < cols; col++ {
// 从宽度1开始，逐步计算不同宽度下的子矩阵
for width := 1; col+width <= cols; width++ {
sum := 0
// 从高度1开始，逐步计算不同高度下的子矩阵
for height := 1; row+height <= rows; height++ {
if col == 0 {
sum += prefixsums[row+height-1][col+width-1]
} else {
sum += prefixsums[row+height-1][col+width-1] - prefixsums[row+height-1][col-1]
}
if sum == target {
fmt.Printf("(%d, %d), width: %d; height: %d\n", row, col, width, height)
ans++
}
}
}
}
}
return ans
}
优化解法
提交AC后，在评论区发现了更为效率的解法。其中，计算每一行的prefix sums仍然是需要的，与基础解法差别在于计算子矩阵和的过程，将2层循环降为了一层，进一步降低了时间复杂度。
核心思想来源于 Subarray Sum Equals to K; 考虑这样的场景：
以点 (0, 0)为左上角，宽度为 w 的子矩阵，从高度1开始，直至最大高度；我们需要判断每一个高度的子矩阵是否满足条件；由于我们已经提前计算出了每一行的 prefix sums，那么对于宽度w下的子矩阵，假设计算后每一行的和为 [s1, s2, s3…]；那么这个问题就变成了： 对于[s1, s2, s3…]，有多少个子数组它的和为target？这个问题就完全等同于 Subarray Sum Equals to K 这个问题了。而这个问题的具体解法如下：
- 假设目标值为k; 计算数组的
prefix sums - 定义一个map, 假设叫
hm，key为某个prefix sum， value表示出现的次数 - 从起始位置开始累加，假设累加和为
sum， 进行如下判断:- 如果在map中 sum-k 存在，则最终答案加上
hm[sum-k] - 如果不存在，则初始化 hm[sum-k] 为1
- 如果在map中 sum-k 存在，则最终答案加上
- 遍历累加结束后，返回最终答案即可
这里略微费解的是，为什么要判断 hm[sum-k]; 我是这么理解的：假设sum是由A[0]~A[n]累加得到，如果hm[sum-k]存在，说明存在这样的一个m (m < n ), 使得 A[m+1]~A[n]的和为k，即存在一个子数组的和为目标值k
因此综上，具体的计算过程如下:
- 首先依然是计算每一行的
prefix sums - 使用2层循环，计算从第一列开始，宽度从1开始的所有情况
- 第3层循环内，从第0行开始，直至最后一行，按照 Subarray Sum Equals to K 问题解法的算法计算子矩阵和，统计满足情况的数量
代码如下:
func numSubmatrixSumTargetV2(matrix [][]int, target int) int {
// 计算每一行的prefix sums
rows := len(matrix)
cols := len(matrix[0])
prefixsums := [][]int{}
for row := 0; row < rows; row++ {
sum := 0
tmp := []int{0}
for col := 1; col <= cols; col++ {
sum += matrix[row][col-1]
tmp = append(tmp, sum)
}
prefixsums = append(prefixsums, tmp)
}
ans := 0
for start := 0; start <= cols; start++ {
for end := start + 1; end <= cols; end++ {
submatricsSum := 0
m := make(map[int]int)
m[0] = 1
for row := 0; row < rows; row++ {
submatricsSum += prefixsums[row][end] - prefixsums[row][start]
if _, ok := m[submatricsSum-target]; ok {
ans += m[submatricsSum-target]
}
m[submatricsSum]++
}
}
}
return ans
}