238. Product of Array Except Self

原答案时间复杂度太高了

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  const ans = []
  for (const i in nums) {
    const tmp = [...nums]
    tmp.splice(i, 1)
    ans.push(tmp.reduce((acc, cur) => acc * cur, 1))
  }
  return ans
}

一句话思路：前后缀分解，ans[i] = prefix[i-1] * surfix[i+1]

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  const n = nums.length
  // prefix
  const prefix = new Array(n + 1).fill(1)
  for (let i = 0; i < n; i++) {
    prefix[i + 1] = nums[i] * prefix[i]
  }
  // surfix
  const surfix = new Array(n + 1).fill(1)
  for (let i = n - 1; i > -1; i--) {
    surfix[i] = nums[i] * surfix[i + 1]
  }
  // get ans
  const ans = []
  console.log(prefix, surfix)
  for (let i = 0; i < n; i++) {
    ans.push(prefix[i] * surfix[i + 1])
  }
  console.log(ans)
  return ans
}

灵神的版本：

定义 pre[i] 表示从 nums[0] 到 nums[i−1] 的乘积。定义 suf[i] 表示从 nums[i+1] 到 nums[n−1] 的乘积。

var productExceptSelf = function (nums) {
  const n = nums.length
  const pre = Array(n)
  pre[0] = 1
  for (let i = 1; i < n; i++) {
    pre[i] = pre[i - 1] * nums[i - 1]
  }

  const suf = Array(n)
  suf[n - 1] = 1
  for (let i = n - 2; i >= 0; i--) {
    suf[i] = suf[i + 1] * nums[i + 1]
  }

  const ans = Array(n)
  for (let i = 0; i < n; i++) {
    ans[i] = pre[i] * suf[i]
  }
  return ans
}

空间优化版本

先计算 suf，然后一边计算 pre，一边把 pre 直接乘到 suf[i] 中。最后返回 suf。

题目说「输出数组不被视为额外空间」，所以该做法的空间复杂度为 O(1)。此外，这种做法比上面少遍历了一次。

var productExceptSelf = function(nums) {
    const n = nums.length;
    const suf = Array(n);
    suf[n - 1] = 1;
    for (let i = n - 2; i >= 0; i--) {
        suf[i] = suf[i + 1] * nums[i + 1];
    }

    let pre = 1;
    for (let i = 0; i < n; i++) {
        // 此时 pre 为 nums[0] 到 nums[i-1] 的乘积，直接乘到 suf[i] 中
        suf[i] *= pre;
        pre *= nums[i];
    }

    return suf;
};

作者：灵茶山艾府
链接：https://leetcode.cn/problems/product-of-array-except-self/solutions/2783788/qian-hou-zhui-fen-jie-fu-ti-dan-pythonja-86r1/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。