238. Product of Array Except Self (1)

Link

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

Solution

第二次作邏輯能想到，但要運算時不太好想起來在同一個array中處理的方法 要先計算Left(i-1)的production然後填入ret[]中，之後再從後面開始算Right[i+1]的production

public class Solution {
public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    //Li-> 由左0到左邊數來第i的乘積
    //Ri-> 由右邊最後一個到左邊數來第i個的乘積
    //output[i] = Li-1 * Ri+1
        
    res[0] = 1;
    //先從前面開始算Li
    for (int i = 1; i < n; i++) {
        res[i] = res[i - 1] * nums[i - 1];
    }
    int right = 1;
    //再從後面開始算Ri+1
    for (int i = n - 1; i >= 0; i--) {
        res[i] *= right;
        right *= nums[i];
    }
    return res;
}