差點忘記來騙騙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
}