題目
#

leetcode 238 - Product of Array Except Self (題目說明請點連結)

題目簡述
#

給一個整數陣列 nums，請返回一個新的陣列 output，其中 output[i] 等於 nums 中除了 nums[i] 之外所有元素的乘積。
注意：請在 O(n) 時間複雜度內完成，且不能使用除法運算。

範例
#

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Explanation: 
- output[0] = 2 × 3 × 4 = 24
- output[1] = 1 × 3 × 4 = 12  
- output[2] = 1 × 2 × 4 = 8
- output[3] = 1 × 2 × 3 = 6

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Explanation: 
- output[0] = 1 × 0 × (-3) × 3 = 0
- output[1] = (-1) × 0 × (-3) × 3 = 0
- output[2] = (-1) × 1 × (-3) × 3 = 9
- output[3] = (-1) × 1 × 0 × 3 = 0
- output[4] = (-1) × 1 × 0 × (-3) = 0

解題思路
#

這題要求我們計算陣列中每個位置除了自己之外所有元素的乘積。由於不能使用除法運算，我們需要巧妙地利用左右乘積的方法來解決這個問題。

解法
#

使用兩個變數 left 和 right 來記錄左右兩側的乘積
第一次遍歷：從左到右，計算每個位置左側所有元素的乘積
第二次遍歷：從右到左，計算每個位置右側所有元素的乘積
將左右乘積相乘得到最終結果

步驟
#

初始化：
- 創建輸出陣列 output，並將所有元素初始化為 1
- 設定左側乘積變數 left = 1
第一次遍歷（左到右）：
- 對於每個位置 i，將 left 乘到 output[i]
- 更新 left = left × nums[i]
第二次遍歷（右到左）：
- 設定右側乘積變數 right = 1
- 對於每個位置 i，將 right 乘到 output[i]
- 更新 right = right × nums[i]
返回結果：
- 返回 output 陣列

例子說明
#

nums = [1, 2, 3, 4]

步驟	位置 i	nums[i]	left	right	output[i]	說明
初始化	-	-	1	-	[1, 1, 1, 1]	創建輸出陣列，所有元素設為 1
第一次遍歷（左到右）	0	1	1	-	[1, 1, 1, 1]	output[0] = 1 × 1 = 1, left = 1 × 1 = 1
第一次遍歷（左到右）	1	2	1	-	[1, 1, 1, 1]	output[1] = 1 × 1 = 1, left = 1 × 2 = 2
第一次遍歷（左到右）	2	3	2	-	[1, 1, 2, 1]	output[2] = 2 × 1 = 2, left = 2 × 3 = 6
第一次遍歷（左到右）	3	4	6	-	[1, 1, 2, 6]	output[3] = 6 × 1 = 6, left = 6 × 4 = 24
第二次遍歷（右到左）	3	4	-	1	[1, 1, 2, 6]	output[3] = 6 × 1 = 6, right = 1 × 4 = 4
第二次遍歷（右到左）	2	3	-	4	[1, 1, 8, 6]	output[2] = 2 × 4 = 8, right = 4 × 3 = 12
第二次遍歷（右到左）	1	2	-	12	[1, 12, 8, 6]	output[1] = 1 × 12 = 12, right = 12 × 2 = 24
第二次遍歷（右到左）	0	1	-	24	[24, 12, 8, 6]	output[0] = 1 × 24 = 24, right = 24 × 1 = 24

最終結果： [24, 12, 8, 6]

計算過程說明：

output[0] = 左側乘積(1) × 右側乘積(2×3×4) = 1 × 24 = 24
output[1] = 左側乘積(1) × 右側乘積(3×4) = 1 × 12 = 12
output[2] = 左側乘積(1×2) × 右側乘積(4) = 2 × 4 = 8
output[3] = 左側乘積(1×2×3) × 右側乘積(1) = 6 × 1 = 6

完整程式碼
#

java

class Solution {
    public int[] productExceptSelf(int[] nums) {
        // 創建輸出陣列，並將所有元素初始化為 1
        int[] output = new int[nums.length];
        Arrays.fill(output, 1);

        // 第一次遍歷：從左到右，計算每個位置左側所有元素的乘積
        int left = 1;
        for(int i = 0; i < nums.length; i++){
            // 將左側乘積乘到當前位置
            output[i] *= left;
            // 更新左側乘積，包含當前元素
            left *= nums[i];
        }

        // 第二次遍歷：從右到左，計算每個位置右側所有元素的乘積
        int right = 1;
        for(int i = nums.length - 1; i >= 0; i--){
            // 將右側乘積乘到當前位置
            output[i] *= right;
            // 更新右側乘積，包含當前元素
            right *= nums[i];
        }

        // 返回結果陣列
        return output;
    }
}

時間複雜度
#

時間複雜度：O(n)，其中 n 是陣列的長度
- 需要兩次遍歷陣列，每次遍歷的時間複雜度都是 O(n)
- 總時間複雜度為 O(2n) = O(n)
空間複雜度：O(1)，不考慮輸出陣列
- 只使用了常數個變數（left 和 right）
- 如果考慮輸出陣列，空間複雜度為 O(n)
- 題目要求返回新陣列，所以輸出陣列不計入額外空間複雜度