算法实战：寻找数组中心下标与除自身外数组乘积（前缀和技巧）

工程师提示：实际面试中，为了节省空间，我们通常只需要维护一个总和变量，遍历时动态计算左侧和即可，无需额外开辟两个数组。这里展示双数组是为了更直观地对应'前缀'与'后缀'的概念。

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

题目描述： 给你一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。 题目要求不使用除法，且时间复杂度为 O(N)。

解题思路： 既然不能用除法，那就不能先算总乘积再除以当前值。我们需要把结果拆分为两部分：

1. 当前位置左侧所有元素的乘积（前缀积）。
2. 当前位置右侧所有元素的乘积（后缀积）。

最终结果 answer[i] = left_product[i] * right_product[i]。

具体步骤如下：

1. 初始化 f 数组记录左侧乘积，g 数组记录右侧乘积。
2. 正向遍历填充 f，反向遍历填充 g。
3. 合并结果。

代码实现：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 1); // 左侧乘积，初始化为 1
        vector<int> g(n, 1); // 右侧乘积，初始化为 1
        vector<int> ret(n);
        
        // 计算左侧前缀积
        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;
    }
};

总结： 这两个问题都展示了前缀和（或前缀积）的核心价值：通过一次线性扫描预处理数据，将后续的查询操作从 O(N) 降为 O(1)。在处理涉及区间统计、累积运算的题目时，优先考虑这种空间换时间的策略，往往能避开暴力解法的性能瓶颈。