解决“统计数组中连续子数组和能被 k整除的个数”问题我们可以通过前缀和 哈希表 同余定理​ 优化时间复杂度从暴力法的 O(n2)降到 O(n)以下是详细解题步骤一、核心思路前缀和与同余定理假设数组的前缀和数组为sumsum[i]表示前i个元素的和sum[0]0sum[1]nums[0]sum[2]nums[0]nums[1]…。对于任意子数组nums[i..j]从第i个到第j个元素其和为sum[j1] - sum[i]。若该子数组和能被 k整除则需满足(sum[j1]−sum[i])%k0根据同余定理上式等价于sum[j1]%ksum[i]%k因此问题转化为统计前缀和余数相同的出现次数——每当遇到与前缀和余数相同的历史记录时这些记录对应的位置到当前位置的子数组和都能被 k整除。二、处理余数的符号问题编程语言中取模运算对负数的处理可能返回负数如 Java 中(-2) \% 5 -2。为保证余数在[0, k-1]范围内需对余数做修正r(sum%kk)%k三、哈希表的作用与初始化哈希表hash键为“前缀和的余数”值为“该余数出现的次数”。初始化必须预先存入0, 1表示“前缀和为 0未遍历任何元素时的余数 0 出现 1 次”——这是为了处理“子数组从数组开头开始”的情况如前缀和本身能被 k整除时。四、算法执行流程以 Java 为例public int subarraysDivByK(int[] nums, int k) { MapInteger, Integer hash new HashMap(); hash.put(0, 1); // 初始前缀和为0余数0出现1次 int sum 0; // 记录当前前缀和 int result 0; // 记录符合条件的子数组数量 for (int x : nums) { sum x; // 计算当前前缀和 // 计算余数处理负数情况 int r (sum % k k) % k; // 历史中出现r的次数都是新增的有效子数组数量 result hash.getOrDefault(r, 0); // 更新当前余数r的出现次数供后续元素使用 hash.put(r, hash.getOrDefault(r, 0) 1); } return result; }五、步骤拆解与示例验证以题目中示例nums [4,5,0,-2,-3,1], k5为例逐步分析遍历元素x当前前缀和sum修正后余数r哈希表操作查增结果result变化初始--hash {0:1}0444查r4→ 0result 0→ 0更新hash {0:1, 4:1}0594查r4→ 1result 1→ 1更新hash {0:1, 4:2}1094查r4→ 2result 2→ 3更新hash {0:1, 4:3}3-272查r2→ 0result 0→ 3更新hash {0:1, 4:3, 2:1}3-344查r4→ 3result 3→ 6更新hash {0:1, 4:4, 2:1}6150查r0→ 1result 1→ 7更新hash {0:2, 4:4, 2:1}7最终返回7与题目示例一致。六、关键总结核心是利用前缀和的差与同余定理将子数组和问题转化为余数统计问题。哈希表用于高效统计余数出现次数避免暴力枚举。余数修正(sum % k k) % k是处理负数的关键保证余数非负。哈希表初始化0, 1是为了覆盖“子数组从数组开头开始”的边界情况。这种方法时间复杂度为 O(n)仅遍历数组一次空间复杂度为 O(k)哈希表最多存 k个不同余数在性能上是高效的。