238. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/description/

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

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

Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Thoughts

依次求出每个数左边的连积和右边的连积。

Code

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

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

Analysis

Errors:

1. 当右边到达0时, res[0]原先的值是0, 应不用乘res[0].

时间复杂度O(N), 无额外空间.