題⽬描述

給定⼀個數組A[0,1,...,n-1] ,請構建⼀個數組B[0,1,...,n-1] ，其中B 中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1] 。不能使⽤除法。（注意：規定B[0] =A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2] ）

對於A ⻓度為1 的情況，B⽆意義，故⽽⽆法構建，因此該情況不會存在。

輸⼊：[1,2,3,4,5]
輸出：[120,60,40,30,24]

思路及解答

暴力

對每個B[i]都計算A中除A[i]外所有元素的乘積，雙重循環，外層遍歷B的每個位置，內層遍歷A數組跳過當前元素

public class Solution {
    public int[] multiply(int[] A) {
        if (A == null || A.length <= 1) {
            return new int[0]; // 根據題目要求，長度<=1時返回空數組
        }
        
        int n = A.length;
        int[] B = new int[n];
        
        // 遍歷每個B[i]
        for (int i = 0; i < n; i++) {
            int product = 1; // 初始化乘積為1
            
            // 計算A中除A[i]外所有元素的乘積
            for (int j = 0; j < n; j++) {
                if (j != i) { // 跳過當前元素A[i]
                    product *= A[j];
                }
            }
            
            B[i] = product; // 將結果存入B[i]
        }
        
        return B;
    }
}

• 時間複雜度：O(n²)，需要嵌套循環遍歷數組

• 空間複雜度：O(1)，除結果數組外只使用常數空間

  左右乘積數組法（空間換時間）

使用左右兩個輔助數組存儲乘積信息

思路：left[i]表示A[0]到A[i-1]的乘積，right[i]表示A[i+1]到A[n-1]的乘積

public class Solution {
    public int[] multiply(int[] A) {
        if (A == null || A.length <= 1) {
            return new int[0];
        }
        
        int n = A.length;
        int[] B = new int[n];
        int[] left = new int[n];  // 存儲左側乘積
        int[] right = new int[n]; // 存儲右側乘積
        
        // 初始化邊界值
        left[0] = 1;     // B[0]沒有左側元素，乘積為1
        right[n-1] = 1;  // B[n-1]沒有右側元素，乘積為1
        
        // 計算左側乘積：left[i] = A[0] × A[1] × ... × A[i-1]
        for (int i = 1; i < n; i++) {
            left[i] = left[i-1] * A[i-1];
        }
        
        // 計算右側乘積：right[i] = A[i+1] × A[i+2] × ... × A[n-1]
        for (int i = n-2; i >= 0; i--) {
            right[i] = right[i+1] * A[i+1];
        }
        
        // 合併左右乘積得到最終結果：B[i] = left[i] × right[i]
        for (int i = 0; i < n; i++) {
            B[i] = left[i] * right[i];
        }
        
        return B;
    }
}

• 時間複雜度：O(n)，三次單層循環
• 空間複雜度：O(n)，需要兩個輔助數組

矩陣視角理解： 如果把問題看作矩陣，B[i]就是去掉對角線元素A[i]後，該行所有元素的乘積。

A = [1, 2, 3, 4, 5]

B[0] = 2 × 3 × 4 × 5 = 120  (去掉A[0])
B[1] = 1 × 3 × 4 × 5 = 60   (去掉A[1])  
B[2] = 1 × 2 × 4 × 5 = 40   (去掉A[2])

左右分解策略：

• left[i]= A[0] × A[1] × ... × A[i-1] （i左邊的乘積）
• right[i]= A[i+1] × A[i+2] × ... × A[n-1] （i右邊的乘積）
• B[i] = left[i] × right[i]（左右乘積相乘正好去掉A[i]）

空間優化（推薦）

在方法二的基礎上優化空間使用，在結果數組B上直接進行左右乘積計算。

先用B數組存儲左側乘積，再用變量動態計算右側乘積

public class Solution {
    public int[] multiply(int[] A) {
        if (A == null || A.length <= 1) {
            return new int[0];
        }
        
        int n = A.length;
        int[] B = new int[n];
        
        // 第一步：計算左側乘積並直接存入B
        B[0] = 1; // B[0]沒有左側元素
        for (int i = 1; i < n; i++) {
            // B[i] = A[0] × A[1] × ... × A[i-1]
            B[i] = B[i-1] * A[i-1];
        }
        
        // 第二步：從右向左遍歷，用temp變量累積右側乘積
        int temp = 1; // 用於累積右側乘積
        for (int i = n-1; i >= 0; i--) {
            // B[i]當前存儲的是左側乘積，乘以右側乘積得到最終結果
            B[i] = B[i] * temp;
            // 更新temp，為下一個位置（i-1）準備右側乘積
            temp = temp * A[i];
        }
        
        return B;
    }
}

• 時間複雜度：O(n)，兩次遍歷數組
• 空間複雜度：O(1)，除結果數組外只使用常數空間

算法步驟詳解

1. 第一步：左側乘積計算

初始: B[0] = 1
i=1: B[1] = B[0] × A[0] = 1 × 1 = 1
i=2: B[2] = B[1] × A[1] = 1 × 2 = 2  
i=3: B[3] = B[2] × A[2] = 2 × 3 = 6
i=4: B[4] = B[3] × A[3] = 6 × 4 = 24
此時B = [1, 1, 2, 6, 24] (存儲的是各位置的左側乘積)

2. 第二步：右側乘積整合

初始: temp = 1
i=4: B[4] = 24 × 1 = 24, temp = 1 × 5 = 5
i=3: B[3] = 6 × 5 = 30, temp = 5 × 4 = 20  
i=2: B[2] = 2 × 20 = 40, temp = 20 × 3 = 60
i=1: B[1] = 1 × 60 = 60, temp = 60 × 2 = 120
i=0: B[0] = 1 × 120 = 120, temp = 120 × 1 = 120
最終B = [120, 60, 40, 30, 24]