一、问题直接转化为前缀和模型
1. 左右前缀积拆分
在处理数组乘积类问题时，如果要求不能使用除法且时间复杂度需控制在 O(n)，我们可以将整体拆分为左前缀积和右前缀积两部分。
以 LeetCode 238 题为例，给定整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。题目保证结果在 32 位整数范围内。
示例：
- 输入：
[1,2,3,4] - 输出：
[24,12,8,6]
思路是将每个位置的乘积分解为左侧所有元素乘积与右侧所有元素乘积的乘积。我们不需要显式地计算整个数组的总乘积再除以当前元素（因为涉及除法且可能有零），而是分别维护两个辅助数组：一个记录当前位置左侧的累积乘积，另一个记录右侧的累积乘积。
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] f = new int[n]; // 左侧前缀积
int[] g = new int[n]; // 右侧前缀积
int[] ret = new int[n];
f[0] = 1;
g[n - 1] = 1;
// 计算左侧前缀积
for (int i = 1; i < n; i++) {
f[i] = f[i - 1] * nums[i - 1];
}
// 计算右侧前缀积
for (int i = n - 2; i >= 0; i--) {
g[i] = g[i + 1] * nums[i + 1];
}
// 合并结果
for (int i = 0; i < n; i++) {
ret[i] = f[i] * g[i];
}
return ret;
}
这种拆分方式避免了除法运算，同时通过两次遍历实现了 O(n) 的时间复杂度。
二、问题转用前缀和
1. 同余性质的本质
当问题涉及子数组和能否被 K 整除时，核心在于利用同余定理。若 (a - b) 能被 p 整除，则 a % p == b % p。
数学表达为：
(a + p*k) % p = a % p
这意味着，如果两个前缀和模 K 的结果相同，那么它们之间的子数组和一定能被 K 整除。
证明
假设 (a - b) / p = k（k 为整数）
=> a - b = p * k
=> a = b + p * k
=> a % p = (b + p * k) % p
=> a % p = b % p
2. 编程语言的取模行为
在实际编码中，不同语言或环境对负数取模的处理可能不同，这直接影响算法的正确性。
计算机取模（向零取整）
大多数编程语言（如 Java、C++）的 % 运算符遵循向零取整规则。余数的符号与被除数相同。
例如：-5 % 3 结果为 -2。
数学定义（向下取整）
数学上的模运算通常遵循向下取整规则，余数始终为非负数。
例如：-5 mod 3 结果为 1。
两者关系与转化
只有在 负数 % 正数 的情况下，两者的结果才会不同（计算机结果为负，数学结果为正）。为了确保逻辑符合数学定义，我们需要进行转化。
标准转化公式为：(a % p + p) % p
这个公式能确保无论 a 是正是负，最终结果都在 [0, p-1] 区间内。
3. 实战代码
基于上述原理，我们可以解决 LeetCode 974 题：和可被 K 整除的子数组。给定整数数组 nums 和整数 k，返回其中元素之和可被 k 整除的非空子数组的数目。
关键在于统计前缀和模 K 相同的次数。如果某个余数出现了 n 次，说明有 n*(n-1)/2 个子数组满足条件。我们在遍历过程中动态累加即可。
public int subarraysDivByK(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int sum = 0;
int ret = 0;
// 初始化：前缀和为 0 的情况视为出现一次
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
// 统一处理负数取模，确保结果非负
int r = (sum % k + k) % k;
// 查找之前是否出现过相同的余数
ret += map.getOrDefault(r, 0);
// 更新当前余数的计数
map.put(r, map.getOrDefault(r, 0) + 1);
}
return ret;
}
注意代码中的 (sum % k + k) % k 这一行，这是处理负数取模的关键，能有效避免负数余数导致的哈希表键值不匹配问题。
