238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

当前数字之外的积等于左边所有数字的积乘以右边所有数字的积。
因此可以维护两个数组，分别计算从左到右的乘积，和从右到左的乘积。

由于返回答案不算占用空间，因此可以将左侧乘积的数组保存在答案数组上。
然后在遍历时，从右至左遍历，使用一个变量储存右边的乘积，直接将两者的乘积更新在答案数组上。
此时空间复杂度为O(1)。

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