一、题目描述——除自身以外数组的乘积

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

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

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

示例 1:

ini
 代码解读
复制代码
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

ini
 代码解读
复制代码
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 输入 保证 数组 answer[i] 在  32 位 整数范围内

进阶： 你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

二、题解(不用除法)

js
 代码解读
复制代码
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const n = nums.length;
    const result = new Array(n).fill(1);

    // 计算前缀乘积
    let prefix = 1;
    for (let i = 0; i < n; i++) {
        result[i] = prefix; // result[i] 存储的是 nums[i] 之前所有元素的乘积。
        prefix *= nums[i];  // prefix 更新为 nums[i] 之前所有元素（包括 nums[i]）的乘积。
    }

    // 计算后缀乘积并与前缀乘积结合
    let suffix = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] *= suffix; // result[i] 现在是 nums[i] 之前所有元素的乘积 * nums[i] 之后所有元素的乘积，即题目所求。
        suffix *= nums[i];  // suffix 更新为 nums[i] 之后所有元素(包括nums[i])的乘积.
    }

    return result;
};

核心思想

这个算法巧妙地利用了两次遍历，分别计算前缀乘积和后缀乘积，并将它们结合起来得到每个位置应有的结果。 由于不能使用除法，我们不能简单地计算所有元素的乘积再除以每个元素。 因此，该方法通过构建前缀和后缀乘积有效地绕过了除法操作。

详细步骤

1. 初始化：

   • n = nums.length; 获取输入数组的长度。
   • result = new Array(n).fill(1); 创建一个大小为 n 的结果数组，并将其所有元素初始化为 1。 这是很关键的一步，所有元素的初始值必须为1，因为它将被用于累积乘积计算。

2. 第一次遍历（计算前缀乘积）：

   • prefix = 1; 初始化前缀乘积为 1。

   • for (let i = 0; i < n; i++) { ... } 从数组的开头到结尾进行遍历。

     • result[i] = prefix; 将 result[i] 设置为当前 prefix 的值。 这里存储的是 nums[0] * nums[1] * ... * nums[i-1] 的乘积。 也就是说，result[i] 存储的是 nums[i] 之前的所有元素的乘积。如果 i 是 0，那么 result[0] 将保持为 1（因为 nums[0] 之前没有元素）。
     • prefix *= nums[i]; 更新 prefix，使其包含到当前元素 nums[i] 的乘积为止。 因此，prefix 始终保持着从 nums[0] 到 nums[i] 所有元素的乘积。

3. 第二次遍历（计算后缀乘积，并与前缀乘积结合）：

   • suffix = 1; 初始化后缀乘积为 1。

   • for (let i = n - 1; i >= 0; i--) { ... } 从数组的结尾到开头进行遍历。

     • result[i] *= suffix; 将 result[i] 乘以当前的 suffix 值。 由于 result[i] 已经包含了 nums[i] 之前所有元素的乘积，而 suffix 包含了 nums[i] 之后所有元素的乘积，因此，result[i] 现在就包含了除了 nums[i] 本身之外的所有元素的乘积。
     • suffix *= nums[i]; 更新 suffix，使其包含到当前元素 nums[i] 的乘积为止。与计算前缀乘积类似，当前的 suffix 始终保持着从 nums[i] 到 nums[n-1]，所有元素的乘积。

4. 返回结果：

   • return result; 返回包含所有结果的数组。

注意事项

1. 数组初始化：  务必将 result 数组的所有元素初始化为 1。这是进行乘法累积操作的基础。 如果初始化为 0，那么最终结果的所有元素都将为 0。
2. 遍历方向：  第一次遍历从前向后，第二次遍历从后向前，这是保证正确计算前缀和后缀乘积的关键。
3. 变量更新顺序：  在每个循环中，先将当前的前缀（或后缀）乘积赋值给结果数组的相应位置，然后再更新前缀（或后缀）乘积。 如果顺序颠倒，结果将不正确。
4. 0 的处理：  如果数组中包含 0，算法仍然可以正常工作。如果数组中只有一个 0，那么结果数组中只有对应于该 0 的位置上的元素是非零的，其他位置上的元素都将是 0。如果数组中包含多个 0，那么结果数组的所有元素都将是 0。 这个行为是符合题意的。
5. 空间复杂度：  该算法的空间复杂度为 O(1)，符合题目要求（输出数组不计入额外空间）。
6. 时间复杂度：  该算法的时间复杂度为 O(n)，因为需要对数组进行两次遍历。

三、结语

再见!