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

除自身以外数组的乘积

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

示例： 输入：nums = [1, 2, 3, 4] 输出：[24, 12, 8, 6] 解释：answer[0] = 2 * 3 * 4 = 24，以此类推。

解法思路

这道题的限制条件比较苛刻，不能用除法，意味着我们不能先算出总乘积再除以当前元素。我们需要分别计算每个位置左侧的乘积和右侧的乘积。

类似于前缀和的思路，我们可以维护两个数组：

1. prefixProd[i] 表示 i 左侧所有元素的乘积（即 nums[0] * ... * nums[i-1]）。
2. suffixProd[i] 表示 i 右侧所有元素的乘积（即 nums[i+1] * ... * nums[n-1]）。

最终结果 answer[i] 即为这两部分的乘积。这样既满足了 O(N) 的时间要求，也避免了除法操作。

C++ 代码实现

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix(n, 1), suffix(n, 1), result(n);
        
        // 计算左侧前缀乘积
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] * nums[i - 1];
        }
        
        // 计算右侧后缀乘积
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] * nums[i + 1];
        }
        
        // 组合结果
        for (int i = 0; i < n; i++) {
            result[i] = prefix[i] * suffix[i];
        }
        
        return result;
    }
};