LeetCode 523. 连续的子数组和（Java）
思路：前缀和 + 哈希表
设 prefix[i] = nums[0] + … + nums[i]。子数组 nums[i+1…j] 的和为 k 的倍数，等价于：
(prefix[j] - prefix[i]) % k == 0 ⇔ prefix[j] % k == prefix[i] % k因此只要两个下标 i < j 的前缀和模 k 的余数相同，且 j - i >= 2（子数组长度至少为 2），就返回 true。
关键技巧：
· map 中只记录每个余数第一次出现的位置（为了让区间尽可能长）。
· 初始化 map.put(0, -1)，这样当下标 i 的余数为 0 时，对应区间为 nums[0…i]，长度 = i - (-1) = i + 1，方便统一判断。
· 长度至少为 2 判断：i - map.get(mod) >= 2。
代码实现
classSolution{publicbooleancheckSubarraySum(int[]nums,intk){// key: 前缀和 % k 的余数// value: 该余数第一次出现的下标Map<Integer,Integer>map=newHashMap<>();map.put(0,-1);// 哨兵：余数 0 在下标 -1 处出现过longprefix=0;for(inti=0;i<nums.length;i++){prefix+=nums[i];intmod=(int)(prefix%k);if(map.containsKey(mod)){// 要求子数组长度至少为 2if(i-map.get(mod)>=2){returntrue;}}else{map.put(mod,i);}}returnfalse;}}示例演示
以 nums = [23, 2, 4, 6, 7], k = 6 为例：
i nums[i] prefix prefix % 6 map 状态 说明
0 23 23 5 {0:-1, 5:0}
1 2 25 1 {0:-1, 5:0, 1:1}
2 4 29 5 5 已存在 i - map[5] = 2 - 0 = 2 >= 2 → 返回 true
子数组 [2, 4] 和为 6，是 6 的倍数。✅
复杂度分析
· 时间复杂度：O(n)，一次遍历，哈希表操作均摊 O(1)。
· 空间复杂度：O(min(n, k))，哈希表最多存 min(n, k) 个不同余数。
易错点
- 只存第一次出现的位置：如果每次出现都覆盖，可能把较长区间的起点覆盖掉，导致结果错误。
- 长度至少为 2：即使发现余数相同，也要检查 i - map.get(mod) >= 2，否则 [k] 这样的单元素子数组会被误判（k 本身是 k 的倍数但长度为 1）。
- 哨兵 map.put(0, -1)：让「从下标 0 开始的子数组和是 k 的倍数」这种情况自然成立，不需要特殊处理。
- 溢出：sum(nums) ≤ 2^31 - 1 时 int 也能放下，但为了稳妥使用 long 累加前缀和。
- k = 0 的边界：LeetCode 约束 1 <= k <= 2^31 - 1，但如果在其他平台遇到 k = 0，需要对 k == 0 单独处理（找是否存在长度 ≥ 2 且和为 0 的连续子数组），因为 % 0 会抛 ArithmeticException。
