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

LeetCode 238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in $O(n)$ time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

method

计算每个nums[i]的前缀积和后缀积，两个相乘就是除了nums[i]外的数组乘积

vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> left(nums.size(), 0);   // 前缀积
    vector<int> right(nums.size(), 0);  // 后缀积
    left[0] = 1;
    for (int i = 1; i < left.size(); i++){
        left[i] = left[i - 1] * nums[i - 1];
    }
    right.back() = 1;
    for (int i = right.size() - 2; i >= 0; i--) {
        right[i] = right[i + 1] * nums[i + 1];
    }
    vector<int> res(nums.size(), 0);
    for (int i = 0; i < nums.size(); i++) {
        res[i] = left[i] * right[i];    // 前缀与后缀的乘积
    }
    return res;
}