企业官网建设流程全解析

解决“统计数组中连续子数组和能被 k整除的个数”问题，我们可以通过前缀和 + 哈希表 + 同余定理​ 优化时间复杂度（从暴力法的 O(n2)降到 O(n)），以下是详细解题步骤：

一、核心思路：前缀和与同余定理

假设数组的前缀和数组为sum（sum[i]表示前i个元素的和，sum[0]=0，sum[1]=nums[0]，sum[2]=nums[0]+nums[1]…）。对于任意子数组nums[i..j]（从第i个到第j个元素），其和为sum[j+1] - sum[i]。

若该子数组和能被 k整除，则需满足：

(sum[j+1]−sum[i])%k=0

根据同余定理，上式等价于：

sum[j+1]%k=sum[i]%k

因此，问题转化为：统计前缀和余数相同的出现次数——每当遇到与前缀和余数相同的历史记录时，这些记录对应的位置到当前位置的子数组和都能被 k整除。

二、处理余数的符号问题

编程语言中，取模运算对负数的处理可能返回负数（如 Java 中(-2) \% 5 = -2）。为保证余数在[0, k-1]范围内，需对余数做修正：

r=(sum%k+k)%k

三、哈希表的作用与初始化

• 哈希表hash：键为“前缀和的余数”，值为“该余数出现的次数”。

• 初始化：必须预先存入<0, 1>，表示“前缀和为 0（未遍历任何元素时）的余数 0 出现 1 次”——这是为了处理“子数组从数组开头开始”的情况（如前缀和本身能被 k整除时）。

四、算法执行流程（以 Java 为例）

public int subarraysDivByK(int[] nums, int k) { Map<Integer, 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], k=5为例，逐步分析：

最终返回7，与题目示例一致。

六、关键总结

• 核心是利用前缀和的差与同余定理将子数组和问题转化为余数统计问题。

• 哈希表用于高效统计余数出现次数，避免暴力枚举。

• 余数修正（(sum % k + k) % k）是处理负数的关键，保证余数非负。

• 哈希表初始化<0, 1>是为了覆盖“子数组从数组开头开始”的边界情况。

这种方法时间复杂度为 O(n)（仅遍历数组一次），空间复杂度为 O(k)（哈希表最多存 k个不同余数），在性能上是高效的。