算法实战：利用前缀和解中心下标与数组乘积问题

28. 除自身以外数组的乘积

题目描述

给你一个整数数组 nums，请你返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

约束条件：

• 不能使用除法。
• 时间复杂度需控制在 O(N)。

解题思路

既然不能用除法，且要求线性时间复杂度，暴力枚举显然不可行。我们需要观察结果的结构。

对于任意位置 i，最终结果 ret[i] 由两部分组成：

1. i 左侧所有元素的乘积：nums[0] * ... * nums[i-1]
2. i 右侧所有元素的乘积：nums[i+1] * ... * nums[n-1]

这本质上就是前缀积和后缀积的结合。我们可以利用两个辅助数组来存储这些信息：

• post[i]：记录 i 位置之前（左侧）所有元素的前缀乘积。
• suf[i]：记录 i 位置之后（右侧）所有元素的后缀乘积。

最后将对应位置的乘积相乘即可得到结果。

C++ 代码实现

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n), g(n), ret(n);
        
        // 初始化边界值，乘法单位元为 1
        f[0] = 1;
        g[n - 1] = 1;
        
        // 计算左侧前缀乘积
        for (int i = 1; i < n; i++) {
            f[i] = f[i - 1] * nums[i - 1];
        }
        
        // 计算右侧后缀乘积
        for (int j = n - 2; j >= 0; j--) {
            g[j] = g[j + 1] * nums[j + 1];
        }
        
        // 合并结果
        for (int i = 0; i < n; i++) {
            ret[i] = f[i] * g[i];
        }
        
        return ret;
    }
};

总结

这两个问题都展示了前缀和（或前缀积）思想在数组处理中的强大之处。

1. 空间换时间：通过预处理构建辅助数组，将原本需要重复计算的子问题结果缓存起来，从而将时间复杂度从 O(N²) 降低到 O(N)。
2. 边界处理：在处理首尾元素时，要注意初始值的设定（求和为 0，求积为 1），这是容易出错的地方。
3. 扩展性：这种模式不仅适用于求和与乘积，还可以推广到其他可结合运算的场景中。