Leetcode/各大家 -- 238. Product of Array Except Self

238. Product of Array Except Self

medium

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

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

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Amazon LinkedIn Apple Facebook Microsoft

     [1,2,3,4]
left [1,1,2,6]
right[24,12,4,1]
res  [24,12,8,6]


思路：Iteration from two side.
          Use left(skip 1st element), right(skip last element) to track product of array.

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        if(nums.length <= 1)return nums;
        int[] res = new int[nums.length];
        res[0] = 1;
        int left = 1, right = 1;
        //left product, skip fist ele (1)
        for(int i = 1; i < nums.length; i++){
            left = nums[i-1]*left;
            res[i] = left;
        }
        //right product, skip last ele
        for(int i = nums.length-2; i >= 0; i--){
            right = nums[i+1]*right;
            res[i] *= right;
        }
        return res;
    }
}