前缀和算法实战：寻找中心下标与除自身外乘积

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

题目链接：

238. 除自身以外数组的乘积 - 力扣（LeetCode）

题目描述：

题目示例：

解法思路

这道题要求不能使用除法，且时间复杂度必须是 O(N)。这意味着我们不能先算出总乘积再除以当前元素。

观察结果数组 ret[i]，它实际上由两部分组成：

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

这其实就是前缀积和后缀积的结合。我们可以分别维护两个数组：

• prefix[i]：表示 nums[0]...nums[i-1] 的乘积。
• suffix[i]：表示 nums[i+1]...nums[n-1] 的乘积。

最终 ret[i] = prefix[i] * suffix[i]。

C++ 代码实现

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix(n, 1), suffix(n, 1), ret(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++) {
            ret[i] = prefix[i] * suffix[i];
        }
        
        return ret;
    }
};

总结

这两道题的核心都在于空间换时间。通过预处理数组存储中间状态（和或积），我们将原本需要重复计算的步骤降到了 O(1)，从而整体将复杂度控制在 O(N)。在实际开发中，遇到类似'区间统计'或'排除当前项'的需求时，不妨先想想能否用前缀和/积来优化。