51.构建乘积数组

题目描述：

给定一个数组 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]。不能使用除法。

示例:

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof

解题思路：

• 这道题给我们一个数组，要求我们将数组的每一位相乘，放入到新的数组中，其中新数组的第i位为所给数组中除了第i位其他所有元素的乘积
• 我们构建两个数组，一个数组的第一位为1，一个数组的最后一位为1
• 对于右边的数组每一位为l[i] = l[i-1] * a[i-1]，i从1开始

• 对于左边的数组每一位为r[i] = r[i+1] * a[i+1]，i从a.length-2开始 | l0 | 1 | 2 | 3 | 4 | 5 | r1 | | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | | l1 | 1 | 1 | 3 | 4 | 5 | r2 | | l2 | 1 | 2 | 1 | 4 | 5 | r3 | | l3 | 1 | 2 | 3 | 1 | 5 | r4 | | l4 | 1 | 2 | 3 | 4 | 1 | r5 |

• 通过图最后我们我每一位为：r1l0，r2l1，r3*l2……..

解题代码：

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