本文共 1331 字，大约阅读时间需要 4 分钟。

解题思路：

要解决这个问题，我们需要为给定的整数数组中每个元素计算其余元素的乘积。为了避免O(n²)的时间复杂度，我们可以使用预先计算左右乘积的方法。

方法1：两次线性遍历

这种方法的时间复杂度是O(n)，因为两次遍历数组的时间都是线性的。

方法2：使用常数空间

为了优化空间复杂度，直接在output数组中存储结果并动态计算：

• 从左到右遍历，计算当前左边的乘积，更新output数组右边的乘积。
• 从右到左遍历，计算当前右边的乘积，更新output数组左边的乘积。
• 具体实现中，动态处理乘积，避免额外数组使用。

这种方法的时间复杂度同样是O(n)，并且空间复杂度为O(1)。

两种方法各有优劣，选择取决于具体需求。首先给出第一种方法，其实现简单直观。

代码实现

public int[] productExceptSelf(int[] nums) {    int n = nums.length;    if (n <= 1) {        return nums;    }    int[] pre = new int[n];    pre[0] = 1;    for (int i = 1; i < n; i++) {        pre[i] = pre[i - 1] * nums[i - 1];    }    int[] suf = new int[n];    suf[n - 1] = 1;    for (int i = n - 2; i >= 0; i--) {        suf[i] = suf[i + 1] * nums[i + 1];    }    int[] res = new int[n];    for (int i = 0; i < n; i++) {        res[i] = pre[i - 1] * suf[i + 1];        if (i == 0) res[i] = suf[i + 1];        if (i == n - 1) res[i] = pre[i - 1];    }    return res;}

代码说明

• 预处理前缀和后缀乘积：

  • pre[0]初始为1，逐渐乘以前一个元素形成前缀。
  • suf[n-1]初始为1，逐渐乘以前一个元素形成后缀。

• 计算每个元素的结果：

  • 当i=0时，结果取pre[0] * suf[1]。
  • 当i=n-1时，结果取pre[n-2] * suf[n-1]。
  • 其它情况下，直接相乘两个数组的值。

这种方法简单明了，能在O(n)时间内完成任务，适合大部分情况。