238. 除自身以外數組的乘積（點擊文末閱讀原文查看題目）
給定長度為 n 的整數數組 nums，其中 n > 1，返回輸出數組 output ，其中 output[i] 等於 nums 中除 nums[i] 之外其餘各元素的乘積。輸入: [1,2,3,4]輸出: [24,12,8,6]說明: 請 不要使用除法，且在 O(n) 時間複雜度內完成此題。進階：
你可以在常數空間複雜度內完成這個題目嗎？（ 出於對空間複雜度分析的目的，輸出數組 不被視為 額外空間。）
解決方案
概述這似乎是一個簡單的問題，可以在線性時間和空間內解決。可以先計算給定數組所有元素的乘積，然後對數組中的每個元素 x ，將乘積除以 x 來求得除自身值的以外的數組乘積。
然後這樣的解決方法有一個問題，就是如果輸入數組中出現 0，那麼這個方法就失效了。而且在問題中說明了不允許使用除法運算。這增加了這個問題的難度。
方法一：左右乘積列表我們不必將所有數字的乘積除以給定索引處的數字得到相應的答案，而是可以利用索引處左側的所有數字乘積和右側所有數字的乘積相乘得到答案。
對於給定索引 i，我們將使用它左邊所有數字的乘積乘以右邊所有數字的乘積。讓我們更加具體的描述這個算法。
初始化兩個空數組 L 和 R。對於給定索引 i，L[i] 代表的是 i左側所有數字的乘積，R[i] 代表的是 i 右側所有數字的乘積。我們需要用兩個循環來填充 L 和 R 數組的值。對於數組 L，L[0]應該是 1，因為第一個元素的左邊沒有元素。對於其他元素：L[i]=L[i-1]*nums[i-1]。同理，對於數組 R，R[length-1] 應為 1。length 指的是輸入數組的大小。其他元素：R[i]=R[i+1]*nums[i+1]。當 R 和 L 數組填充完成，我們只需要在輸入數組上迭代，且索引 i處的值為：L[i]*R[i]。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 reversed(range(length - 1)): R[i] = nums[i + 1] * R[i + 1] for i in range(length): answer[i] = L[i] * R[i] return answerclass Solution { public int[] productExceptSelf(int[] nums) {
int length = nums.length;
int[] L = new int[length]; int[] R = new int[length];
int[] answer = new int[length];
L[0] = 1; for (int i = 1; i < length; i++) {
L[i] = nums[i - 1] * L[i - 1]; }
R[length - 1] = 1; for (int i = length - 2; i >= 0; i--) {
R[i] = nums[i + 1] * R[i + 1]; }
for (int i = 0; i < length; i++) { answer[i] = L[i] * R[i]; }
return answer; }}複雜度分析
時間複雜度：O(N)，其中 N 指的是輸入數組的大小。空間複雜度：O(N)，使用了 L 和 R 數組去構造答案。方法二：空間複雜度 O(1) 的方法儘管上面的方法已經能夠很好的解決這個問題，但是不是常數的空間複雜度。由於輸出數組不算在空間複雜度內，那麼我們可以將 L 或 R 數組在用輸出數組來計算，然後再動態構造另一個。讓我們來看看基於這個思想的算法。初始化 answer 數組，對於給定索引 i，answer[i] 代表的是 i左側所有數字的乘積。這種方法的唯一變化就是我們沒有構造 R 數組。而是用一個遍歷來跟蹤右邊元素的乘積。並更新數組 answer[i] = answer[i] * R。然後 R 更新為 R = R* nums[i]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] = nums[i - 1] * answer[i - 1] R = 1; for i in reversed(range(length)): answer[i] = answer[i] * R R *= nums[i] return answerclass Solution { public int[] productExceptSelf(int[] nums) {
int length = nums.length;
int[] answer = new int[length];
answer[0] = 1; for (int i = 1; i < length; i++) {
answer[i] = nums[i - 1] * answer[i - 1]; }
int R = 1; for (int i = length - 1; i >= 0; i--) {
answer[i] = answer[i] * R; R *= nums[i]; }
return answer; }}複雜度分析
時間複雜度：O(N)，其中 N 指的是輸入數組的大小。空間複雜度：O(1)，問題的描述中說明了輸出數組不算空間複雜度。點個在看，少個 bug👇