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

难度：🟡 Medium | 标签：前缀积、数组 | 状态：⬜ LeetCode 链接

思路

不能用除法，且 O(1) 额外空间（结果数组不算）。

两次扫描：

1. 第一遍：res[i] = 左侧所有元素的乘积
2. 第二遍：用变量 right 维护右侧累积，乘进 res[i]

代码

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 1);
        for (int i = 1; i < n; ++i) res[i] = res[i - 1] * nums[i - 1];
        int right = 1;
        for (int i = n - 1; i >= 0; --i) {
            res[i] *= right;
            right *= nums[i];
        }
        return res;
    }
};

复杂度

• 时间 O(n)，空间 O(1)（不计输出）

易错 / 回顾

• 不允许除法（题目要求）—— 因为有 0 时直接除会错
• 第二遍要用一个标量 right，不能再开数组
• 0 的处理天然正确：左积 / 右积自动跳过自己