前缀和算法实战：区间乘积与整除子数组

二、问题转化为前缀和模型

再看 LeetCode 974 题，求和可被 K 整除的子数组数目。这类问题通常涉及区间和的计算，而区间和可以通过前缀和快速推导。

1. 同余性质分析

若一个区间 [j, i] 的和能被 k 整除，即 (sum[i] - sum[j]) % k == 0。这意味着 sum[i] 和 sum[j] 对 k 取模的结果必须相同。

公式推导如下： (a + p*k) % p = a % p

2. 同余定理推导

如果差值能被整除，即 (a - b) % p == 0，那么 a 和 b 模 p 的余数必然相等。

证明： 假设 (a - b) / p = k（k 为整数） => a - b = p * k => a = b + p * k => a % p = (b + p * k) % p => a % p = b % p

3. 取模运算的差异

在实现时，我们需要特别注意编程语言中取模运算符 % 的行为与数学定义的差异，尤其是在处理负数时。

3.1 计算机取模规则

大多数编程语言（如 Java、C++）中的 % 运算符遵循'向零取整'的规则。

• 向零取整相除：余数的绝对值最接近 0。
• 符号：结果的符号与被除数相同。

例如 -5 % 3 在计算机中结果为 -2。

3.2 数学定义

数学上的模运算通常遵循'向下取整'的规则。

• 向下取整相除：余数为正值且最接近 0。
• 符号：结果始终为正数（当除数为正时）。

例如 -5 mod 3 在数学上结果为 1。

3.3 差异与转化

只有在 负数 % 正数 的情况下，两者的结果才会不同（计算机为负，数学为正）。为了统一处理，我们需要将计算机的取模结果转化为数学意义上的非负余数。

转化公式为：(a % p + p) % p

基于上述原理，我们可以利用哈希表统计前缀和模 k 的出现次数。如果当前前缀和模 k 的值之前出现过，说明中间这段区间的和能被 k 整除。

public int subarraysDivByK(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    int sum = 0;
    int ret = 0;
    
    // 初始化：前缀和为 0 的情况出现一次（对应从索引 0 开始的子数组）
    map.put(0, 1);
    
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        // 关键步骤：处理负数取模，确保余数在 [0, k-1] 范围内
        int r = (sum % k + k) % k;
        
        // 如果该余数之前出现过，累加之前的次数
        ret += map.getOrDefault(r, 0);
        
        // 更新当前余数的计数
        map.put(r, map.getOrDefault(r, 0) + 1);
    }
    return ret;
}

通过这种方式，我们将原本需要 O(n^2) 暴力枚举的问题优化到了 O(n)。