[Leetcode]238 : Product of Array Except Self

Link : https://leetcode.com/problems/product-of-array-except-self/

Problem :
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.

有一個array nums ，回傳一個result且result[i]為除了nums[i]的所有元素的乘積和。注意：不要使用除法且在time complexity = O(n)。

圖來自leetcode

nums = [1, 2, 3, 4]
result = [2*3*4, 1*3*4, 1*2*4, 1*2*3] = [24, 12, 8, 6]

Thoughts:
1. 因為有除法的限制，所以不能全部先乘完，然後再用除法再把自己除掉。
2. 因為不用乘法，可以分為兩個部分，數字 i 前面的乘積、數字 i 後面的乘積。
3. 用一個 result 來把前面的乘積、後面的乘積做相乘。

Steps :
nums = [ 1, 2, 3, 4] #從2開始往後跑迴圈
new1 = [ 1, 1, 1, 1]
new1 update = [ 1, 1*1, 1*2*1, 2*3*1] = [ 1, 1, 2, 6]

nums = [ 1, 2, 3, 4] #從3開始往前跑迴圈
new2 = [ 1, 1, 1, 1]
new2 update = [ 2*3*4*1, 3*4*1, 4*1, 1] = [ 24, 12, 4, 1]

new1 update* new2 update = [ 1, 1, 2, 6]*[ 24, 12, 4, 1] = [1*24, 1*12, 2*4, 6*1] = [ 24, 12, 8, 6]

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        rtol = [1]*length
        ltor = [1]*length
        result = [1]*length
        if not nums:
            return []
        # i從1到長度
        for i in range(1,length):
            rtol[i] = rtol[i-1]* nums[i-1]
        # 從length到-1的整數序列(遞增值為-1)。
        for i in range(length-2,-1,-1):
            ltor[i] = ltor[i+1]* nums[i+1]
        for i in range(length):
            result[i] = rtol[i]*ltor[i]
        return result

time complexity = O(n)