除自身以外数组的乘积

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

题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

• 2 <= nums.length <= 10⁵
• -30 <= nums[i] <= 30
• 输入保证数组 answer[i] 在 32 位整数范围内

解题思路：

第一次遍历正向构建前缀积存入 res，第二次反向遍历维护后缀积 next，两者相乘即为结果。全程 O(n) 时间、O(1) 额外空间（输出数组不计）。

初版思路（两个辅助数组）：

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

优化版（O(1) 额外空间）：

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 next=1;
        for(int i=n-1;i>=0;i--){
            res[i]=next*res[i];
            next=next*nums[i];
        }
        return res;
    }
};

python

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n: int = len(nums)
        res: List[int] = [1] * n
        for i in range(1, n, 1):
            res[i] = res[i - 1] * nums[i - 1]
        nxt: int = 1
        for i in range(n - 1, -1, -1):
            res[i] = res[i] * nxt
            nxt = nxt * nums[i]
        return res

go

func productExceptSelf(nums []int) []int {
    var n int = len(nums)
    var res []int = make([]int, n)
    res[0] = 1
    for i := 1; i < n; i++ {
        res[i] = res[i-1] * nums[i-1]
    }
    var next int = 1
    for i := n - 1; i >= 0; i-- {
        res[i] = next * res[i]
        next = next * nums[i]
    }
    return res
}

java

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        res[0] = 1;
        for (int i = 1; i < n; i++) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        int next = 1;
        for (int i = n - 1; i >= 0; i--) {
            res[i] = next * res[i];
            next = next * nums[i];
        }
        return res;
    }
}