题目描述#

给你一个整数数组 nums 和一个整数 k，判断是否存在一个长度至少为 2 的连续子数组，使得该子数组元素和是 k 的倍数。

等价地说，是否存在下标区间 [l, r]（r - l + 1 >= 2），满足：

• (nums[l] + nums[l+1] + ... + nums[r]) % k == 0

如果存在返回 true，否则返回 false。

知识边界#

这份解法的核心是“前缀和 + 同余”。

• 设 prefix[i] 表示前 i 个元素的和（prefix[0] = 0）。
• 子数组 nums[l...r] 的和为 prefix[r+1] - prefix[l]。
• 若该和是 k 的倍数，则有： prefix[r+1] % k == prefix[l] % k。

因此问题变成：

• 是否存在两个前缀下标 i 和 j（i > j），满足
  1. prefix[i] % k == prefix[j] % k
  2. i - j > 1（保证子数组长度至少为 2）

实现上用哈希表记录“某个余数第一次出现的位置”。

• 如果当前余数之前出现过，并且下标差大于 1，直接返回 true。
• 如果没出现过，记录当前下标（只记录第一次，保证区间尽量长、容易满足长度条件）。

复杂度：

• 时间复杂度 O(n)
• 空间复杂度 O(min(n, k))（以实际余数种类计）

代码#

func checkSubarraySum(nums []int, k int) bool {
 prefix := make([]int, len(nums)+1)
 for i, x := range nums {
 prefix[i+1] = prefix[i] + x
 }
 cnt := make(map[int]int)
 cnt[0] = 0
 // 只要两个前缀和对 k 取模相同，它们之间的子数组和就是 k 的倍数。
 for i := 0; i < len(prefix); i++ {
 mod := prefix[i] % k
 if id, ok := cnt[mod]; ok {
 if i-id > 1 {
 return true
 }
 } else {
 cnt[mod] = i
 }
 }
 return false
}