Re: [閒聊] 每日LeetCode已回收
我用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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.139.166.212 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706436917.A.9D1.html
→
01/28 18:16,
1年前
, 1F
01/28 18:16, 1F
→
01/28 18:16,
1年前
, 2F
01/28 18:16, 2F
那是三小
推
01/28 18:18,
1年前
, 3F
01/28 18:18, 3F
※ 編輯: JIWP (223.139.166.212 臺灣), 01/28/2024 18:20:20
→
01/28 18:20,
1年前
, 4F
01/28 18:20, 4F
推
01/28 18:22,
1年前
, 5F
01/28 18:22, 5F
→
01/28 18:24,
1年前
, 6F
01/28 18:24, 6F
推
01/28 18:27,
1年前
, 7F
01/28 18:27, 7F
→
01/28 18:29,
1年前
, 8F
01/28 18:29, 8F
→
01/28 18:38,
1年前
, 9F
01/28 18:38, 9F
→
01/28 18:38,
1年前
, 10F
01/28 18:38, 10F
討論串 (同標題文章)
完整討論串 (本文為第 625 之 719 篇)：