問題

https://leetcode.com/problems/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.

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]

Constraints:

2 <= nums.length <= 105
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

提示

如何初始化一個固定長度的陣列，且所有元素都是自定的初始值

Python

a = [1] * 5 # a = [1, 1, 1, 1, 1]

Go

Go 無法像 Python 一樣建立一個含自定初始值的陣列．
它只能先用 make 函數建立一個固定長度的陣列，其所有元素的值都是 0．
然後我們在利用迴圈來給予每個元素自定的初始值．
例如：

func main() {
	n := 5
	ans := make([]int, n)
	for i := range ans {
		ans[i] = 1
	}
	fmt.Println(ans)
}

我的答案

方法 1: 兩個陣列紀錄乘積

先分成計算每個元素（nums[i]）的左邊(left)跟右邊(right)的乘積
left[i] = nums[i]左邊的乘積
= nums[0] * nums[1] * ... * nums[i-2] * nums[i-1]
= left[i-1] * nums[i-1]

right[i]= nums[i]右邊的乘積
= nums[i+1] * nums[i+2] * ... * nums[n-1]
= nums[i+1] * right[i+1]

最後再把 left[i] * right[i] 就是答案

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        l = len(nums)
        left = [1] * l
        right = [1] * l

        for i in range(1, l):
            left[i] = left[i-1]*nums[i-1]

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

        for i in range(l):
            left[i] = left[i] * right[i]

        return left

方法 2: 將方法 1 中 right 陣列一個變數取代

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left = [1] * n
        right = 1

        for i in range(1, l):
            left[i] = left[i-1]*nums[i-1]

        for i in range(n-2, -1, -1):
            right = right * nums[i+1]
            left[i] = left[i] * right

        return left

Go

func productExceptSelf(nums []int) []int {
    n := len(nums)
    left := make([]int, n)
    right := 1

    left[0] = 1
    for i := 1 ; i < n ; i++ {
        left[i] = left[i-1]*nums[i-1]
    }

    for i := n-2 ; i > -1 ; i-- {
        right = right * nums[i+1]
        left[i] = left[i] * right
    }

    return left
}