差点忘记来骗骗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
}