每日連續200天了，好耶
523. Continuous Subarray Sum
給一個整數array nums和一個整數k
請判斷nums是否包含good subarray
subarray的定義
(1)至少有兩個元素
(2)subarray的合是k的倍數
思路:
如果有兩個數a、b，除以k的餘數相等則(a-b)%k==0
所以用prefix sum的概念
用sum記錄到目前為止所有元素的總和
並且用一個hash table紀錄sum%k第一次出現的index
如果目前sum%k在之前已經出現過且index相差2以上就回傳true
golang code:
func checkSubarraySum(nums []int, k int) bool {
if len(nums) < 2 {
return false
}
modMap, sum := make(map[int]int), 0
modMap[0] = -1
for i, num := range nums {
sum += num
mod := sum % k
if prevIndex, exists := modMap[mod]; exists {
if i - prevIndex >= 2 {
return true
}
} else {
modMap[mod] = i
}
}
return false
}