## [238\. 除自身以外數組的乘積](https://leetcode-cn.com/problems/product-of-array-except-self/) >Medium #### 思路 **題目幾點要求** * 不能使用**除法** * 時間復雜度為`$ O(n) $` ----- * 時間復雜度為`$ O(n) $`，換句話說，就是一層遍歷，不能用循環嵌套。但是我們可以多次遍歷 * 除自身以外的乘積，我們可以分解為：元素左側的乘積 * 元素右側的乘積 * 假如是邊界，側邊沒有元素我們給1，應為乘積不受影響 * 題目進階讓我們在常數空間中操作，這樣我們要用一個騷操作，使用dp中滾動數組的思想，減少空間復雜度 * 利用滾動數組的思想，以左側為例，向右移動一位，歷史的乘積在乘上當前元素左側的數據，也就是移動新增的一位，就是當前節點左側所有元素的乘積 ``` left → right #1 value 1 2 3 4 ↑ left 1 right #2 value 1 2 3 4 ↑ left 1 1 right #3 value 1 2 3 4 ↑ left 1 1 2 right #4 value 1 2 3 4 ↑ left 1 1 2 6 right left ← right #1 value 1 2 3 4 ↑ left 1 1 2 6 right 1 #2 value 1 2 3 4 ↑ left 1 1 2 6 right 4 1 #3 value 1 2 3 4 ↑ left 1 1 2 6 right 12 4 1 #4 value 1 2 3 4 ↑ left 1 1 2 6 right 24 12 4 1 -------------------- left * right result 24 12 8 6 ``` 實際我們也不需要兩個數組，只需在一個數組上進行操作即可。 綜上，嘗試寫一下代碼，AC！ #### 代碼 python3 ``` class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: result = [1] * len(nums) for i in range(1, len(nums)): result[i] = result[i-1] * nums[i-1] k = 1 for j in range(len(nums)-1, -1, -1): result[j] *= k k *= nums[j] return result ```