推 CanIndulgeMe: 再内卷的话，真的卷不动了 06/09 23:14
→ JIWP: 寶我現在是寫興趣的 06/09 23:15
推 CanIndulgeMe: 羡慕擅长于编程的大神 06/09 23:19
差點忘記來騙騙p幣
等下來聽日文
974. Subarray Sums Divisible by K
給一個整數array nums和一個整數k
請問nums中有幾個subarray的總和可以被k整除
思路:
基本就跟昨天一樣
prefix sum的概念
用sum記錄到目前為止的總和
hash table rec紀錄到目前為止餘數sum%k出現的次數
要注意會出現負數
所以要多一個判斷式當sum%k<0 sum%k+=k
接著每次都去加sum%k就可以得到答案了
golang code:
func subarraysDivByK(nums []int, k int) int {
rec := make(map[int]int)
rec[0] = 1
sum, res := 0, 0
for _, val := range nums {
sum += val
tmp := sum % k
if tmp < 0 {
tmp += k
}
res += rec[tmp]
rec[tmp]++
}
return res
}
--
https://i.imgur.com/r9FBAGO.gif
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.34.11 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1717946022.A.FCB.html