剑指offer67_构建乘积数组

构建乘积数组

给定一个数组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]。

不能使用除法。

数据范围

输入数组长度 [0,20]。

样例

输入：[1, 2, 3, 4, 5]

输出：[120, 60, 40, 30, 24]

思考题：

• 能不能只使用常数空间？（除了输出的数组之外）

算法思路

核心思想：
将 B[i] 拆解为 左乘积（left[i]） × 右乘积（right[i]）：

1. 左乘积：A[0] × A[1] × ... × A[i-1]（即 i 左侧所有元素的乘积）。
2. 右乘积：A[i+1] × A[i+2] × ... × A[n-1]（即 i 右侧所有元素的乘积）。

通过两次遍历分别计算左乘积和右乘积，最终合并结果。

• 时间复杂度：O(n)
  仅需两次线性遍历数组，无嵌套循环。
• 空间复杂度：O(1)（不考虑输出数组 B）
  仅使用常数个临时变量（p）。若考虑输出数组，则为 O(n)。

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int n = A.size();
        vector<int> B(n);  // 初始化结果数组
        if (A.empty()) return B;  // 边界条件：空数组直接返回

        // 第一遍遍历：计算左乘积（B[i] = A[0] × A[1] × ... × A[i-1]）
        for (int i = 0, p = 1; i < n; i++) {
            B[i] = p;  // 存储左乘积
            p *= A[i]; // 更新左乘积（累乘A[i]）
        }

        // 第二遍遍历：计算右乘积并合并结果（B[i] *= A[i+1] × A[i+2] × ... × A[n-1]）
        for (int i = n - 1, p = 1; i >= 0; i--) {
            B[i] *= p;  // 左乘积 × 右乘积
            p *= A[i];   // 更新右乘积（反向累乘A[i]）
        }

        return B;
    }
};

实例演示（以 A = [1, 2, 3, 4] 为例）

步骤分解：

1. 初始化：
   B = [1, 1, 1, 1]（初始值）
2. 第一次遍历（计算左乘积）：
   • i=0: B[0]=1, p=1×1=1
   • i=1: B[1]=1, p=1×2=2
   • i=2: B[2]=2, p=2×3=6
   • i=3: B[3]=6, p=6×4=24
     此时 B = [1, 1, 2, 6]（左乘积结果）
3. 第二次遍历（计算右乘积并合并）：
   • i=3: B[3]=6×1=6, p=1×4=4
   • i=2: B[2]=2×4=8, p=4×3=12
   • i=1: B[1]=1×12=12, p=12×2=24
   • i=0: B[0]=1×24=24, p=24×1=24
     最终 B = [24, 12, 8, 6]

验证：

• B[0] = 2 × 3 × 4 = 24
• B[1] = 1 × 3 × 4 = 12
• B[2] = 1 × 2 × 4 = 8
• B[3] = 1 × 2 × 3 = 6
  结果正确 ✅

关键点

1. 避免除法：通过分解为左、右乘积的乘法操作。
2. 空间优化：复用输出数组 B 存储中间结果，减少额外空间。
3. 两次遍历：第一次正向遍历计算左乘积，第二次反向遍历计算右乘积并合并。