除自身以外数组的乘积

在这篇文章中，我们将深入探讨经典的“乘积数组谜题”。虽然这个问题早在多年前就被提出，但在 2026 年的今天，随着 AI 辅助编程的普及和异构计算的兴起，重新审视这个算法能让我们对空间局部性和现代工程实践有更深刻的理解。

[更优方法] 使用前缀和后缀数组 – O(n) 时间和 O(n) 空间

让我们思考一下这个场景：如果我们能够预先计算出某个索引左侧所有数字的乘积（前缀积）和右侧所有数字的乘积（后缀积），那么最终结果无非就是这两个值的乘积。这就是我们常说的“空间换时间”策略。

> 核心逻辑：res[i] = 左侧乘积 * 右侧乘积。这种方法避免了重复计算，将时间复杂度从 O(n^2) 降到了 O(n)，但代价是需要额外的 O(n) 空间来存储前缀和后缀数组。

在我们的最近的一个高频交易系统微服务项目中，这种预计算模式非常常见，但我们需要极其小心内存的分配效率。让我们来看看具体的实现：

C++

#include 
#include 
using namespace std;

vector productExceptSelf(vector& arr) {
    int n = arr.size();
    if (n == 0) return {};

    // 初始化前缀和后缀数组
    // 我们在这里预留空间以避免动态扩容带来的性能损耗
    vector prefix(n, 1);
    vector suffix(n, 1);
    vector res(n, 1);

    // 计算前缀积：prefix[i] 存储的是 arr[i] 左侧所有元素的乘积
    // 注意：prefix[0] 左侧没有元素，保持为 1
    for (int i = 1; i = 0; i--) {
        suffix[i] = suffix[i + 1] * arr[i + 1];
    }

    // 合并结果
    for (int i = 0; i < n; i++) {
        res[i] = prefix[i] * suffix[i];
    }

    return res;
}

int main() {
    vector arr = {10, 3, 5, 6, 2};
    vector res = productExceptSelf(arr);
    for (int val : res) 
        cout << val << " ";
    return 0;
}
    

CODEBLOCK_5147917f


Java

import java.util.Arrays;

class GfG {
    static int[] productExceptSelf(int[] arr) {
        int n = arr.length;
        int[] prefix = new int[n];
        int[] suffix = new int[n];
        int[] res = new int[n];

        // 填充默认值
        Arrays.fill(prefix, 1);
        Arrays.fill(suffix, 1);

        // 前向遍历计算前缀
        for (int i = 1; i = 0; i--) {
            suffix[i] = suffix[i + 1] * arr[i + 1];
        }

        // 组合结果
        for (int i = 0; i < n; i++) {
            res[i] = prefix[i] * suffix[i];
        }

        return res;
    }

    public static void main(String[] args) {
        int[] arr = {10, 3, 5, 6, 2};
        int[] res = productExceptSelf(arr);
        for (int val : res) System.out.print(val + " ");
    }
}
    

INLINECODEd3c34a76resINLINECODE6bf3a2b1resINLINECODEd49aa062suffixINLINECODE18e1fee3

Python

def productExceptSelf(arr):
    n = len(arr)
    res = [1] * n

    # 第一遍：构建前缀积并存储在 res 中
    for i in range(1, n):
        res[i] = res[i-1] * arr[i-1]

    suffix_prod = 1
    # 第二遍：从右向左，结合后缀积
    for i in range(n-1, -1, -1):
        res[i] *= suffix_prod
        suffix_prod *= arr[i]

    return res

if __name__ == "__main__":
    arr = [10, 3, 5, 6, 2]
    print(productExceptSelf(arr))
    

CODEBLOCK_e681a6e9


JavaScript

function productExceptSelf(arr) {
    let n = arr.length;
    let res = new Array(n).fill(1);

    // 第一轮：构建前缀积
    for (let i = 1; i = 0; i--) {
        res[i] = res[i] * suffixProd;
        suffixProd *= arr[i];
    }

    return res;
}

// Driver code
let arr = [10, 3, 5, 6, 2];
let res = productExceptSelf(arr);
console.log(res.join(" "));
    

INLINECODE8defab4freduceINLINECODE8cc675bereduceINLINECODE91211946forINLINECODEd7348e6dBigIntINLINECODE898a48cf0INLINECODEd3f462f70INLINECODEd92ec31a0INLINECODE27eb583eintINLINECODEf7612b17long longINLINECODEb6a8e3f6longINLINECODEde440c78BigIntINLINECODEf7d336b8[1, 2, 3]INLINECODE620bf4fc[100, 100, 100]INLINECODEcaf54b1b[0, 1, 2]INLINECODE06c9d7f8log(a*b) = log(a) + log(b)INLINECODE27eaccfbiINLINECODEa4ed50eclog(arr[i])INLINECODE9b6c81d3expINLINECODE5cf0174e0INLINECODEb156835blog, exp`）的开销远大于整数乘法。

总结与 2026 展望

通过这篇文章，我们从经典的嵌套循环出发，探讨了 O(n) 空间的前缀/后缀解法，最终实现了 O(1) 辅助空间的高效算法。这不仅是一道面试题，更是理解“预计算”和“空间复用”设计模式的绝佳案例。

随着 Agentic AI（自主智能体）的发展，未来的算法优化可能不再仅仅是人类手工的优化，而是 AI 编译器根据硬件特性自动进行的重写。但无论如何，理解这些基础原理，将帮助你写出更符合现代硬件架构的高效代码，让你在面对“AI 生成的平庸代码”时，拥有优化和重构的底气。