---
# System prepended metadata

title: '**Leetcode筆記(Product of Array Except Self)**'
tags: [arrays, medium, leetcode]

---

# **Leetcode筆記(Product of Array Except Self)**


:::info
:information_source: 題目 : Product of Array Except Self, 類型 : arrays , 等級 : medium
日期 : 2023/02/17，2023/05/02，2023/06/26，2023/10/11，2024/10/02
:::


### 嘗試

錯誤想法，我先把全部的值先乘起來，但若遇到list中有零的話，總product即會為零
```python
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        product = 1
        for val in nums:
            product = val * product
        record = list()
        for i, val in enumerate(nums):
            product1 = product / val
            record.insert(i, product1)
```
2023/05/02
```python
for i, n in enumerate(reversed(nums)):
# 若nums = [1,2,3,4]
# 印出來的會是0 4 /// 1 3 /// 2 2 /// 3 1 ///
# i 還是會從0開始


# 用兩個array 
# 對一個數字來說 一個array儲存其前面所有數字的乘積
# 另一個array儲存其後面的所有數字的乘積
# 兩個array相乘 即是答案


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        prefix = [1] * len(nums)
        postfix = [1] * len(nums)
        res = [1] * len(nums)

        temp_pre = 1
        
        for i, n in enumerate(nums):
            prefix[i] = temp_pre
            temp_pre = temp_pre * n
        
        temp_post = 1
        
        for i, n in enumerate(reversed(nums)):
            # 要修正 因為i還是從0開始
            postfix[len(nums) - 1 - i] = temp_post
            temp_post = temp_post * n
        
        for i in range(len(nums)):
            res[i] = postfix[i] * prefix[i]
        
        return res
```
2023/06/26
把左邊和右邊兩個array乘起來
```python
for i, c in enumerate(nums[::-1]):
回傳的c會是倒著的，但是i會是從0~len(nums) - 1的正常輸出

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

        # nums = [1,2,3,4]
        # prefix = [1, 1, 2, 6]
        # postfix = [24, 12, 4, 1]
        # ans = [24, 12, 8, 6]
        tempPre = 1
        for i, c in enumerate(nums):
            prefix[i] = tempPre
            tempPre *= c

        tempPost = 1
        for i, c in enumerate(nums[::-1]):
            postfix[len(nums) - i - 1] = tempPost
            tempPost *= c
        
        res = [1] * len(nums)
        for i in range(len(nums)):
            res[i] = prefix[i] * postfix[i]

        return res
```
2023/10/11
酷喔，竟然自己做出來了
```python
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1] * len(nums)
        tmp = nums[0]
        for i in range(1, len(nums)):
            res[i] = tmp * res[i]
            tmp = tmp * nums[i]

        tmp = nums[-1]
        for i in range(len(nums) - 2, -1, -1):
            res[i] = tmp * res[i]
            tmp = tmp * nums[i]
        
        return res
```
2024/10/02
```python
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        prefix, suffix, res = [1] * n, [1] * n, [1] * n

        for i in range(1, n):
            prefix[i] = nums[i - 1] * prefix[i - 1]
        
        for i in range(n - 2, -1, -1):
            suffix[i] = nums[i + 1] * suffix[i + 1]
        
        for i in range(n):
            res[i] = prefix[i] * suffix[i]
        
        return res
```

---
### **優化**

postfix和prefix去略過待計算值，空間複雜度O(n)，因為沒用到額外記憶體，時間複雜度O(n)

```python
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        prefix = 1
        output = [1] * len(nums)
        # ex. nums = [1,2,3,4] 
        for i in range(len(nums)): # i = 0, 1, 2, 3
            output[i] = prefix # 1, 1, 2, 6
            prefix = prefix * nums[i] # 1, 2, 6

        postfix = 1
        for i in  reversed(range(len(nums))): # i = 3, 2, 1, 0
            output[i] = output[i] * postfix # postfix = 1, 4, 12, 24  output = 6, 8, 12, 24
            postfix = postfix * nums[i] # 4, 12, 24
        
        return output
```
---


**:warning: 錯誤語法** 
:::warning

:::


**:thumbsup:學習** 
:::success
range(5) -> 為0, 1, 2, 3, 4
創規定長度的空list -> [1] * len(nums)
reversed(range(5)) -> 4 3 2 1 0
range(4,-1,-1) -> 4 3 2 1 0
:::

**思路**
![](https://i.imgur.com/cyugrUa.png)


**講解連結**
https://www.youtube.com/watch?v=bNvIQI2wAjk
Provided by. NeetCode

###### tags: `arrays` `leetcode` `medium`