0238. 除自身以外数组的乘积【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 前缀后缀乘积

1. 📝 题目描述

• leetcode

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

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

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

---

示例 1：

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2：

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

---

提示：

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

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

2. 🎯 s.1 - 前缀后缀乘积

c

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* res = (int*)malloc(sizeof(int) * numsSize);
    res[0] = 1;
    for (int i = 1; i < numsSize; i++) {
        res[i] = res[i - 1] * nums[i - 1];
    }
    int right = 1;
    for (int i = numsSize - 1; i >= 0; i--) {
        res[i] *= right;
        right *= nums[i];
    }
    return res;
}

js

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  const n = nums.length
  const res = new Array(n)
  res[0] = 1
  for (let i = 1; i < n; i++) {
    res[i] = res[i - 1] * nums[i - 1]
  }
  let right = 1
  for (let i = n - 1; i >= 0; i--) {
    res[i] *= right
    right *= nums[i]
  }
  return res
}

py

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [1] * n
        for i in range(1, n):
            res[i] = res[i - 1] * nums[i - 1]
        right = 1
        for i in range(n - 1, -1, -1):
            res[i] *= right
            right *= nums[i]
        return res

• 时间复杂度：$O(n)$，其中 $n$ 是数组长度
• 空间复杂度：$O(1)$，输出数组不计入额外空间

算法思路：

• 第一次从左往右遍历，计算每个位置左侧所有元素的乘积
• 第二次从右往左遍历，乘以右侧所有元素的乘积