238.除自身以外数组的乘积

链接：238.除自身以外数组的乘积
难度：Medium
标签：数组、前缀和
简介：给你一个长度为  n  的整数数组  nums，其中  n > 1，返回输出数组  output ，其中 output[i]  等于  nums  中除  nums[i]  之外其余各元素的乘积。

题解 1 - typescript

• 编辑时间：2020-06-04
• 执行用时：132ms
• 内存消耗：42.7MB
• 编程语言：typescript
• 解法介绍：虽通过但使用了除法不符合题目要求

function productExceptSelf(nums: number[]): number[] {
  let zeroIndex = nums.indexOf(0);
  if (zeroIndex === -1) {
    let sum = 1;
    for (const num of nums) sum *= num;
    return nums.map(v => sum / v);
  } else if (nums.includes(0, zeroIndex + 1)) {
    return nums.map(v => 0);
  } else {
    let sum = 1;
    for (const num of nums) sum *= num === 0 ? 1 : num;
    return nums.map(v => (v === 0 ? sum : 0));
  }
}

题解 2 - typescript

• 编辑时间：2020-06-04
• 执行用时：132ms
• 内存消耗：42.1MB
• 编程语言：typescript
• 解法介绍：储存左值与右值,res[i]=l[i]*r[i]

function productExceptSelf(nums: number[]): number[] {
  const len = nums.length;
  let l: number[] = [];
  let r: number[] = [];
  l[0] = 1;
  for (let i = 1; i < len; i++) l[i] = l[i - 1] * nums[i - 1];
  r[len - 1] = 1;
  for (let i = len - 2; i >= 0; i--) r[i] = r[i + 1] * nums[i + 1];
  return nums.map((_, i) => l[i] * r[i]);
}

题解 3 - typescript

• 编辑时间：2020-06-04
• 执行用时：96ms
• 内存消耗：42MB
• 编程语言：typescript
• 解法介绍：根据题解 2，利用输出数组，先存入左值再累乘右值，使空间变 O(1)

function productExceptSelf(nums: number[]): number[] {
  const len = nums.length;
  let ans: number[] = [1];
  for (let i = 1; i < len; i++) ans[i] = ans[i - 1] * nums[i - 1];
  let r = nums[len - 1];
  for (let i = len - 2; i >= 0; i--) {
    ans[i] *= r;
    r *= nums[i];
  }
  return ans;
}