238. Product of Array Except Self (M)

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]

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

题意

给定一个数组nums，要求返回一个新数组output，满足以下条件：

限制时间复杂度为，且不能使用除法。

思路

output[i]相当于在nums中将nums[i]左边所有数和nums[i]右边所有数累乘。因此可以采取类似于动态规划的操作：先从左到右遍历一遍nums，记录当前位置所有左侧数字之积；再从右到左遍历一遍nums，记录当前位置所有右侧数字之积，将两者相乘后得到的就是output。可以只使用一个output数组来达到的空间复杂度。

代码实现

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