除自身以外数组的乘积

数组前缀积

题目描述

给定一个整数数组 nums，返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

要求：

不允许使用除法。
时间复杂度为 O(n)。

思路分析

如果直接对每个位置重新遍历一遍数组并计算乘积，时间复杂度会达到 O(n^2)，不满足题目要求。

更高效的做法是把每个位置的答案拆成两部分：

该位置左侧所有元素的乘积
该位置右侧所有元素的乘积

只要把这两部分相乘，就得到了当前位置“除自身以外”的乘积。

具体来说：

第一趟遍历，计算每个位置左侧所有元素的乘积，并存入结果数组 answer。
第二趟从右向左遍历，用变量 right 维护当前位置右侧所有元素的乘积，再与 answer[i] 相乘。

这样就能在不使用除法的前提下，用两次线性遍历完成计算。

算法步骤

初始化结果数组 answer，长度与 nums 相同，初始值全部为 1。
从左到右遍历数组，让 answer[i] 表示 nums[i] 左侧所有元素的乘积。
定义变量 right = 1，表示当前位置右侧元素乘积的初始值。
从右到左遍历数组，将 answer[i] *= right。
每处理完一个位置后，更新 right *= nums[i]，供下一个位置使用。

示例代码

/**
 * @param nums - 整数数组
 * @returns 返回一个新数组，其中每个位置的值等于原数组中除当前元素外其余元素的乘积
 *
 * @example
 * productExceptSelf([1, 2, 3, 4]) // [24, 12, 8, 6]
 * productExceptSelf([-1, 1, 0, -3, 3]) // [0, 0, 9, 0, 0]
 */
export function productExceptSelf(nums: number[]): number[] {
    // 记录数组长度，后面会多次用到，避免重复写 nums.length。
    const len = nums.length;
    // 创建结果数组 answer，长度和 nums 一样，先全部填成 1，方便后续做乘法累积。
    const answer = new Array(len).fill(1);

    // 从左往右遍历，计算每个位置左边所有元素的乘积。
    for (let i = 1; i < len; i++) {
        // answer[i - 1] 是“前一个位置左边所有元素的乘积”，再乘上 nums[i - 1]，
        // 就得到了“当前位置左边所有元素的乘积”。
        answer[i] = answer[i - 1] * nums[i - 1];
    }

    // right 表示“当前位置右边所有元素的乘积”，一开始右边没有元素，所以初始值是 1。
    let right = 1;
    // 从右往左遍历，把右边乘积和前面已经算好的左边乘积合并起来。
    for (let i = len - 1; i >= 0; i--) {
        // answer[i] 当前存的是左边乘积，乘上 right 之后，就变成“除自己以外所有元素的乘积”。
        answer[i] = answer[i] * right;
        // 更新 right：把当前元素 nums[i] 也乘进去，供左边一个位置继续使用。
        right *= nums[i];
    }

    // 返回最终结果数组。
    return answer;
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组长度。只需要两次线性遍历。
空间复杂度：O(1)，如果不计返回数组 answer，只额外使用了一个变量 right。

示例演示

以 nums = [1, 2, 3, 4] 为例：

第一趟遍历后，answer 中保存的是每个位置左侧元素乘积：

下标	nums[i]	answer[i]（左侧乘积）
0	1	1
1	2	1
2	3	2
3	4	6

第二趟从右向左遍历：

下标	当前 `right`	更新后的 `answer[i]`
3	1	6
2	4	8
1	12	12
0	24	24

最终结果为：

[24, 12, 8, 6]

#除自身以外数组的乘积

#题目描述

#思路分析

#算法步骤

#示例代码

#复杂度分析