LeetCode 523. 连续的子数组和Java思路前缀和 哈希表设 prefix[i] nums[0] … nums[i]。子数组 nums[i1…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: 该余数第一次出现的下标MapInteger,IntegermapnewHashMap();map.put(0,-1);// 哨兵余数 0 在下标 -1 处出现过longprefix0;for(inti0;inums.length;i){prefixnums[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。
