LeetCode 熱題 100 | 238. 除自身以外數組的乘積

大家好，今天我們來解決一道經典的算法問題——除自身以外數組的乘積。這道題在 LeetCode 上被標記為中等難度，要求在不使用除法的情況下，計算數組中每個元素的乘積，其中每個元素的值是數組中除自身以外其余各元素的乘積。

---

問題描述

給你一個整數數組 nums，返回數組 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘積。

題目數據保證數組 nums 之中任意元素的全部前綴元素和后綴的乘積都在 32 位整數范圍內。

示例 1：

輸入: nums = [1,2,3,4]
輸出: [24,12,8,6]

示例 2：

輸入: nums = [-1,1,0,-3,3]
輸出: [0,0,9,0,0]

提示：

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• 輸入保證數組 answer[i] 在 32 位整數范圍內

---

解題思路

核心思想

1. 前綴和后綴乘積：

   • 使用兩個數組 left 和 right 分別存儲每個位置的前綴乘積和后綴乘積。
   • left[i] 表示從數組開頭到位置 i-1 的所有元素的乘積。
   • right[i] 表示從位置 i+1 到數組末尾的所有元素的乘積。
   • 最終結果 answer[i] 為 left[i] * right[i]。

2. 優化空間復雜度：

   • 可以直接在結果數組 answer 中計算前綴乘積，然后從后向前計算后綴乘積，從而避免使用額外的數組。

---

Python代碼實現

class Solution:def productExceptSelf(self, nums: List[int]) -> List[int]:n = len(nums)answer = [1] * n# 計算前綴乘積left_product = 1for i in range(n):answer[i] = left_productleft_product *= nums[i]# 計算后綴乘積并更新結果right_product = 1for i in range(n - 1, -1, -1):answer[i] *= right_productright_product *= nums[i]return answer

代碼解析

1. 初始化：

   • answer 數組初始化為長度為 n 的列表，所有值初始化為 1。

2. 計算前綴乘積：

   • 使用變量 left_product 記錄當前元素之前的乘積。
   • 遍歷數組，更新 answer[i] 為 left_product，然后更新 left_product。

3. 計算后綴乘積并更新結果：

   • 使用變量 right_product 記錄當前元素之后的乘積。
   • 從后向前遍歷數組，更新 answer[i] 為 answer[i] * right_product，然后更新 right_product。

4. 返回結果：

   • 最終結果存儲在 answer 中。

---

復雜度分析

• 時間復雜度：O(n)，其中 n 是數組 nums 的長度。只需要兩次遍歷數組。
• 空間復雜度：O(1)，直接在結果數組 answer 中計算，不使用額外的數組。

---

示例運行

示例 1

輸入: nums = [1,2,3,4]
輸出: [24,12,8,6]

示例 2

輸入: nums = [-1,1,0,-3,3]
輸出: [0,0,9,0,0]

---

總結

通過前綴和后綴乘積的方法，我們可以高效地解決除自身以外數組的乘積問題。這種方法在 O(n) 時間復雜度內完成，并且只使用了常數級別的額外空間。希望這篇題解對大家有所幫助，如果有任何問題，歡迎在評論區留言討論！

關注我，獲取更多算法題解和編程技巧！