每日连续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
}