[Leetcode] 238. Product of Array Except Self

題目 : 238. Product of Array Except Self Medium

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.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

# 不能用除法 時間限制O(n)

# nums = [1, 2, 3, 4]

# answer = [24,12, 8, 6]

# 24 = 2 * 3 * 4 left = 1 reght = 2*3*4

# 12 = 1 * * 3 * 4 left = 1 reght = 3*4

# 8 = 1 * 2 * 4 left = 1*2 reght = 4

# 6 = 1 * 2 * 3 left = 1*2*3 reght = 1

# left = [1,1,2,6] ->

# right = [24,12,4,1] <-

# answer = left*right = [24,12,8,6]

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        

        length = len(nums)

        L, R, answer = [0]*length, [0]*length, [0]*length

        L[0] = 1
        for i in range(1, length):
            L[i] = nums[i-1] * L[i-1]

        R[length-1] = 1
        for i in range(length-2, -1, -1):
            R[i] = R[i+1] * nums[i+1]

        for i in range(length):
            answer[i] = R[i] * L[i] 

        return answer

2. 只使用1個陣列存取

line 7 : 因為第1個元素的左邊沒有值可以相乘，所以直接assign 1給它

line 8 : 先將左邊的部分存到anwer陣列中

line 11 : buff是暫存右邊乘積的數值，倒數第1個元素的右邊沒有值，所以assign 1 給它

line 12 : 設1個for迴圈，從倒數第2個元素開始做計算，將原先存在answer的左邊乘積乘上buff(右邊乘積)，即可得出最後的答案

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        length = len(nums)

        answer = [0]*length
        answer[0] = 1
        for i in range(1,length):
            answer[i] = answer[i-1] * nums[i-1]
        
        buff = 1
        for i in range(length-2, -1, -1):
            buff *= nums[i+1]
            answer[i] *= buff 

        return answer