238. [M] Product of Array Except Self

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

基本思路

对于结果数组output的元素i，其值是输入数组中左边所有元素的乘积 乘以 右边所有元素的乘积。 output[i] = product(0..i-1) * product(i+1..input.length-1)

为了避免使用除法，所以要算两遍，第一遍从左往右遍历输入数组，累计计算左边所有元素的乘积。第二遍从右往左遍历，计算所有右边元素的乘积。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] output = new int[nums.length];
        
        output[0] = 1;
        for (int i = 1, p = nums[0]; i < nums.length; i++) {
            output[i] = p;
            p *= nums[i];
        }
        for (int i = nums.length - 2, p = nums[nums.length-1]; i >= 0; i--) {
            output[i] *= p;
            p *= nums[i];
        }
        return output;
    }
}

时间复杂度 O(n)，空间复杂度 O(1)