除了自身以外数组的乘积

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟡 中等
核心考察点：数组、前缀和（前缀积）

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

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1：
输入：nums = [1,2,3,4]
输出：[24,12,8,6]
解释：
索引 0: 234 = 24
索引 1: 134 = 12
索引 2: 124 = 8
索引 3: 123 = 6

示例 2：
输入：nums = [-1,1,0,-3,3]
输出：[0,0,9,0,0]

2. 解题思路拆解

方法：左右乘积列表（前后缀分解）

题目要求不能使用除法。如果能用除法，我们只需要算出所有数的乘积，然后除以当前数即可（当然要注意 0 的情况）。

既然不能用除法，我们可以把问题拆解： answer[i] = (nums[0]...nums[i-1]) * (nums[i+1]...nums[n-1]) 也就是：左边所有数的乘积 * 右边所有数的乘积。

计算左侧乘积：
- 创建一个数组 L，L[i] 表示索引 i 左侧所有元素的乘积。
- L[0] = 1（左边没有元素，乘积初始为 1）。
- L[i] = L[i-1] * nums[i-1]。
计算右侧乘积：
- 同理，我们可以创建一个数组 R，R[i] 表示索引 i 右侧所有元素的乘积。
- 但为了节省空间（题目进阶要求 $O(1)$ 空间），我们不需要显式创建 R 数组。
- 我们可以用一个变量 R 来动态记录右侧乘积，从右向左遍历，直接乘到 L[i] 上。
合并结果：
- 最终 answer[i] = L[i] * R。

3. 代码实现

javascript

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const n = nums.length;
    const answer = new Array(n);
    
    // 1. 先利用 answer 数组存储左侧乘积
    // answer[i] 表示 i 左边所有元素的乘积
    answer[0] = 1;
    for (let i = 1; i < n; i++) {
        answer[i] = answer[i - 1] * nums[i - 1];
    }
    
    // 2. 动态计算右侧乘积，并直接更新 answer
    let R = 1; // R 表示 i 右边所有元素的乘积
    for (let i = n - 1; i >= 0; i--) {
        // 当前位置的结果 = 左侧乘积 * 右侧乘积
        answer[i] = answer[i] * R;
        
        // 更新 R，为下一个位置（更左边的位置）做准备
        R = R * nums[i];
    }
    
    return answer;
};

代码执行演示

输入 nums = [1, 2, 3, 4]

第一轮遍历（左侧乘积）：
- answer[0] = 1
- answer[1] = 1 * 1 = 1
- answer[2] = 1 * 2 = 2
- answer[3] = 2 * 3 = 6
- 此时 answer = [1, 1, 2, 6]
第二轮遍历（右侧乘积 + 合并）：
- 初始化 R = 1
- i = 3: answer[3] = 6 * 1 = 6。R = 1 * 4 = 4。
- i = 2: answer[2] = 2 * 4 = 8。R = 4 * 3 = 12。
- i = 1: answer[1] = 1 * 12 = 12。R = 12 * 2 = 24。
- i = 0: answer[0] = 1 * 24 = 24。R = 24 * 1 = 24。

最终结果：[24, 12, 8, 6]。

4. 复杂度分析

维度	描述
时间复杂度	$O(n)$。我们进行了两次遍历，每次遍历都是线性的。
空间复杂度	$O(1)$。输出数组 `answer` 不被视为额外空间。我们只使用了常数个额外变量。

除了自身以外数组的乘积 ​

1. 题目呈现 ​

2. 解题思路拆解 ​

方法：左右乘积列表（前后缀分解） ​

3. 代码实现 ​

代码执行演示 ​