题目描述

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

• 标签：数组遍历
• 这道题目如果可以使用除法，就比较简单了，先求出所有数的乘积，然后再依次除掉每个对应的值即可。
• 不让使用除法，那么最简单的思路就是将B[i]的每个位置都把所需要的数乘一遍，但是这样的时间复杂度就非常高了。
• 降低时间复杂度的方法就是以 A[i]为界限，分割出左右三角形，其中每个三角形从尖部到底部都是可以积累的，这样就可以减少时间复杂度。

算法流程

• 1 首先声明结果数组 res
• 2 求出左侧三角从上到下的值，依次存入 res[i] 中
• 3 求出右侧三角从上到下的值并且和之前的 res[i]做乘积存入，即可得到结果

代码

/**
 * @param {number[]} a
 * @return {number[]}
 */
var constructArr = function(a) {
  let res = [];
  let left = 1;
  for (let i = 0; i < a.length; i++) {
    res[i] = left;
    left *= a[i];
  } 
  let right = 1;
  for (let i = a.length - 1; i >= 0; i--) {
    res[i] *= right;
    right *= a[i];
  }
  return res;
};