题目

给定一个整数数组 nums，请你返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

要求：

• 不能使用除法
• 时间复杂度为 O(n)

---

示例 1

输入：
nums = [1, 2, 3, 4]

输出：
[24, 12, 8, 6]

解释：

• answer[0] = 2 * 3 * 4 = 24
• answer[1] = 1 * 3 * 4 = 12
• answer[2] = 1 * 2 * 4 = 8
• answer[3] = 1 * 2 * 3 = 6

---

示例 2

输入：
nums = [-1, 1, 0, -3, 3]

输出：
[0, 0, 9, 0, 0]

解释：

• 对于包含 0 的数组，其余元素的乘积会受到影响。

---

提示

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• 保证 数组 nums 中任意元素的所有前缀与后缀的乘积都在 32 位整数范围内。

实现

class Solution {
private:
    static const int N = 1e5 + 10;
    int preMul[N] , preMulRev[N]; // 正逆序求累计乘积
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        preMul[0] = 1  , preMulRev[nums.size() + 1] = 1;

        for(int i = 0 ; i < nums.size() ; i++) {
            preMul[i + 1] = preMul[i] * nums[i];
            preMulRev[nums.size() - i] = preMulRev[nums.size() - i + 1] * nums[nums.size() - i - 1];
        }

        vector<int> res;

        for(int i = 1 ; i <= nums.size() ; i++) {
            res.push_back(preMul[i-1] * preMulRev[i+1]);
        }
        return res;
    }
};