前缀和算法进阶：拆分、同余与取模处理

前缀和算法进阶：拆分、同余与取模处理

在前缀和的基础原理之上，实际解题中往往需要更灵活的变形。今天重点聊聊它在两种典型场景下的应用：直接拆分乘积，以及利用同余定理处理子数组求和。

拆分思路：除自身以外数组的乘积

遇到类似 LeetCode 238 题这种要求'除自身外其余元素乘积'的问题，且限制不能使用除法时，我们可以把结果拆解为'左侧所有元素的乘积'乘以'右侧所有元素的乘积'。

具体做法是维护两个辅助数组（或者优化空间），一个记录当前位置左侧的累积乘积，另一个记录右侧的累积乘积。这样每个位置的结果就是左右两部分的拼接。

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] f = new int[n], g = new int[n], ret = new int[n];
    f[0] = 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;
}

同余定理：和可被 K 整除的子数组

再看 LeetCode 974 题，求和能被 K 整除的子数组数量。这里的核心在于利用前缀和的差值性质。如果区间 [j, i] 的和能被 K 整除，即 ，那么必然有 。