Product of Array Except Self

Given an array ofnintegers wheren> 1,nums, return an arrayoutputsuch thatoutput[i]is equal to the product of all the elements ofnumsexceptnums[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.)

题意：这道题给定我们一个数组，让我们返回一个新数组，对于每一个位置上的数是其他位置上数的乘积，并且限定了时间复杂度O(n)，并且不让我们用除法。

分析

Given numbers[2, 3, 4, 5], regarding the third number 4, the product of array except 4 is2*3*5which consists of two parts: left2*3and right5. The product isleft*right. 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).

We store lefts in result array. If we allocate a new array for rights. The space complexity is O(n). To make it O(1), we just need to store it in a variable which isrightin @lycjava3’s code.

代码

class Solution {
     public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        // Calculate lefts and store in res.
        int left = 1;
        for (int i = 0; i < n; i++) {
            if (i > 0)
                left = left * nums[i - 1];
                res[i] = left;
        }
        // Calculate rights and the product from the end of the array.
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1)
                right = right * nums[i + 1];
                res[i] *= right;
        }
        return res;
    }
}