算法实战：寻找数组中心下标与除自身外数组乘积

关键点说明：

• 初始化时 f[0] 和 g[n-1] 默认为 0，无需显式赋值，因为循环范围避开了它们。
• 空间复杂度为 O(N)，若追求极致优化，可先求总和 total，遍历时用 total - leftSum - nums[i] 代替右侧和，将空间降为 O(1)。

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

题目描述： 给你一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。题目数据保证数组中任意元素的前缀和后缀乘积在 32 位整数范围内。请不要使用除法，且要求在 O(N) 时间复杂度内完成。

解题思路： 这道题的限制条件很明确：不能用除法，必须 O(N)。 对于任意位置 i，结果由两部分组成：

1. i 左侧所有元素的乘积（前缀积）
2. i 右侧所有元素的乘积（后缀积）

因此，我们可以复用前缀和的思路，构建两个辅助数组：

• pre[i]：存储 nums[0] * ... * nums[i-1] 的乘积。
• suf[i]：存储 nums[i+1] * ... * nums[n-1] 的乘积。 最终结果 ans[i] = pre[i] * suf[i]。

代码实现：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n, 1), suf(n, 1), ans(n);
        
        // 计算前缀积：pre[i] 包含 i 左侧所有元素
        for (int i = 1; i < n; ++i) {
            pre[i] = pre[i - 1] * nums[i - 1];
        }
        
        // 计算后缀积：suf[i] 包含 i 右侧所有元素
        for (int i = n - 2; i >= 0; --i) {
            suf[i] = suf[i + 1] * nums[i + 1];
        }
        
        // 组合结果
        for (int i = 0; i < n; ++i) {
            ans[i] = pre[i] * suf[i];
        }
        
        return ans;
    }
};

进阶思考： 上述解法使用了 O(N) 的额外空间。实际上，我们可以利用输出数组 ans 来暂存前缀积，再用一个变量动态维护后缀积，从而将空间复杂度优化至 O(1)（不计输出数组）。这在面试中常作为加分项提出。

总结

这两个问题虽然场景不同，但核心都是利用'拆分'思想：将整体问题拆解为左半部分和右半部分的独立计算，再通过预处理避免重复运算。掌握这种前缀和/前缀积的模式，能帮你快速应对大量涉及区间统计、累积计算的算法题。