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].

Follow up:

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

Tips:

从左乘一次，从右乘一次，每次都错开i上的数。

第一次可以得到这个数左边的所有数的积，第二次再乘上右边的就可以了。

O(n), O(1)

Given numbers [2, 3, 4, 5], regarding the third number 4, the product of array except 4 is 235 which consists of two parts: left 23 and right 5. The product is leftright. We can get lefts and rights:

Numbers:     2    3    4     5
Lefts:            2  2*3 2*3*4
Rights:  3*4*5  4*5    5      

Let’s fill the empty with 1:

Numbers:     2    3    4     5
Lefts:       1    2  2*3 2*3*4
Rights:  3*4*5  4*5    5     1

We can calculate lefts and rights in 2 loops. The time complexity is O(n).

Code:

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