代碼訓練(24)LeetCode之數組乘積

Author: Once Day Date: 2025年6月5日

漫漫長路，才剛剛開始…

全系列文章可參考專欄: 十年代碼訓練_Once-Day的博客-CSDN博客

參考文章:

• 238. 除自身以外數組的乘積 - 力扣（LeetCode）
• 力扣 (LeetCode) 全球極客摯愛的技術成長平臺

1. 原題

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

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

請 **不要使用除法，**且在 O(n) 時間復雜度內完成此題。

提示：

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

示例：

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

2. 分析

我們需要計算一個數組 answer，其中每個元素 answer[i] 是原數組 nums 中除了 nums[i] 之外所有元素的乘積。關鍵點是我們不能使用除法，并且需要在 O(n) 時間復雜度內解決，同時盡量減少額外空間的使用。

題目提供了一個數組 nums，要求我們為每一個元素計算出它所有其他元素的乘積。使用除法的話會非常直接，但題目要求我們不能使用除法，因此我們需要找到其他方法。由于每個元素的結果是其他元素的乘積，我們可以將問題分解為兩部分的乘積：當前元素左側的所有元素的乘積和右側所有元素的乘積。

解題思路

1. 構建左積數組 L，其中 L[i] 表示 nums[i] 左側所有元素的乘積。
2. 構建右積數組 R，其中 R[i] 表示 nums[i] 右側所有元素的乘積。
3. 計算結果數組 answer，其中 answer[i] = L[i] * R[i]。

分析步驟

構建左積數組：

• 初始化 L[0] = 1（因為第一個元素左邊沒有元素）。
• 從左到右遍歷 nums，每個 L[i] = L[i - 1] * nums[i - 1]。

構建右積數組：

• 初始化 R[n-1] = 1（因為最后一個元素右邊沒有元素）。
• 從右到左遍歷 nums，每個 R[i] = R[i + 1] * nums[i + 1]。

計算結果數組：

• answer[i] = L[i] * R[i]。

舉例分析，以示例 nums = [1,2,3,4]：

構建 L:

• L[0] = 1
• L[1] = 1 (L[0] * nums[0])
• L[2] = 2 (L[1] * nums[1])
• L[3] = 6 (L[2] * nums[2])

構建 R：

• R[3] = 1
• R[2] = 4 (R[3] * nums[3])
• R[1] = 12 (R[2] * nums[2])
• R[0] = 24 (R[1] * nums[1])

結果 answer:

• answer[0] = L[0] * R[0] = 1 * 24 = 24
• answer[1] = L[1] * R[1] = 1 * 12 = 12
• answer[2] = L[2] * R[2] = 2 * 4 = 8
• answer[3] = L[3] * R[3] = 6 * 1 = 6

性能優化關鍵點

• 時間復雜度：O(n)。我們只需要三次遍歷整個數組。
• 空間復雜度：可以優化到 O(1)（不包括輸出數組）。我們可以直接在輸出數組上構建 L，然后用一個變量來跟蹤右邊元素的乘積。

3. 代碼實現

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {int i;*returnSize = numsSize;int *returnArray = malloc(numsSize * sizeof(int));// Build the answer array as left product arrayreturnArray[0] = 1;for (i = 1; i < numsSize; i++) {returnArray[i] = returnArray[i - 1] * nums[i - 1];}// Modify the answer array by multiplying with right productsint right = 1;for (i = numsSize - 1; i >= 0; i--) {returnArray[i] = returnArray[i] * right;right *= nums[i];}return returnArray;
}

4. 總結

這道題測試了對數組操作和優化的理解。通過空間復雜度優化，我們學習了如何利用已有的資源（輸出數組和變量）減少空間需求。要提升編程能力，關鍵在于練習如何將問題分解成小的部分，并高效地解決它們。此外，學習如何通過一些小技巧（如變量跟蹤）在有限的資源下完成任務也是很重要的。