楼主:
JIWP (JIWP)
2024-01-28 18:15:15我用hash table + prefix sum
写起来也没有4个循环快
一定是我太烂了
太苦了
func numSubmatrixSumTarget(matrix [][]int, target int) int {
n := len(matrix)
m := len(matrix[0])
prefix := make([][]int, n+1)
ans := 0
for i := 0; i < n+1; i++ {
prefix[i] = make([]int, m+1)
}
for i := 1; i < n+1; i++ {
for k := 1; k <= i; k++ {
rec := make(map[int]int)
for j := 1; j < m+1; j++ {
prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j]
[i-1][j-1]
sum := prefix[i][j] - prefix[i-k][j]
if sum == target {
ans++
}
diff := sum - target
ans += rec[diff]
rec[sum]++
}
}
}
return ans
}