力扣 1074. 元素和为目标值的子矩阵数量
给出矩阵 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’），那么这两个子矩阵也不同。
方案一：通过枚举上下边界，并将边界内的元素压缩，然后套用优美子数组 中前缀和的方案。
func numSubmatrixSumTarget(matrix [][]int, target int) (ans int) {
// 通过枚举上下边界来列举所有可能的子矩阵
// 枚举上边界
for top := 0; top < len(matrix); top++ {
sum := make([]int, len(matrix[0]))
// 枚举下边界
for bottom := top; bottom < len(matrix); bottom++ {
// 压缩元素
for i, v := range matrix[bottom] {
sum[i] += v
}
// 计算结果
ans += numberOfSubarrays(sum, target)
}
}
return
}
// 优美子数组前缀和方案
func numberOfSubarrays(nums []int, k int) (ans int) {
mp := make(map[int]int)
mp[0] = 1
preSum := 0
for _, num := range nums {
preSum += num
// curr presum - some previous presum == k 则表明有满足条件的子数组
if v, ok := mp[preSum - k]; ok {
ans += v
}
mp[preSum]++
}
return
}
- 时间复杂度：O(m * m * n)，m 为行数，n 为列宽，因为嵌套 for 循环，枚举上下边界时会造成 O(m * m) 的时间复杂度， 在枚举过程中还有一个嵌套的 for 循环用作计算压缩上下边界和的临时数组，其时间复杂度为 O(m)，所以时间复杂度为 O(m * m * n)。
- 空间复杂度：O(n)， 因为需要一个容量为 n 的数组保存压缩后的临时结果，所以空间复杂度为 O(n)。