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

解析

此題給予一個陣列字串num，要求回傳一陣列，該陣列中的每個元素必須是原陣列中其他元素相乘的乘積，並且不能用除法來解。難度為Medium。

可宣告兩個陣列L及R，L陣列的第一個元素為1，其餘每個元素皆為L陣列的前一個元素與nums陣列中相對位置的前一個元素之乘積，即L[i] = L[i−1] * nums[i−1]。
R陣列的最後一個元素為1，其餘每個元素皆為R陣列的後一個元素與nums陣列中相對位置的後一個元素之乘積，即R[i] = R[i+1] * nums[i+1]。
最後將兩陣列相對位置的元素一一相乘並儲存到新陣列，所得到的新陣列即為所求。

Follow up要求空間複雜度為O(1)，可透過先前宣告的L或R陣列，將該陣列中的元素逐次乘以一變數，該變數初始值為1，之後該變數逐次乘上nums陣列中相對位置的值，因為題目說回傳的陣列其空間複雜度不計，則最後得到的陣列即為所求。

解法

時間複雜度：O(N)
空間複雜度：O(N)

class Solution {
    public int[] productExceptSelf(int[] nums) {

        int length = nums.length;
        int[] L = new int[length];
        int[] R = new int[length];
        int[] answer = new int[length];

        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }

        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }

        for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }
        return answer;
    }
}

Follow up解法

時間複雜度：O(N)
空間複雜度：O(1)

class Solution {
    public int[] productExceptSelf(int[] nums) {

        int length = nums.length;
        int[] answer = new int[length];
        
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
        }
        
        int R = 1;
        for (int i = length - 1; i >= 0; i--) {
            answer[i] = answer[i] * R;
            R *= nums[i];
        }
        return answer;
    }
}

備註

希望透過記錄解題的過程，可以對於資料結構及演算法等有更深一層的想法。
如有需訂正的地方歡迎告知，若有更好的解法也歡迎留言，謝謝。