剑指offer66(Java)-构建乘积数组（中等）

题目：

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 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]
 

提示：

• 所有元素乘积之和不会溢出 32 位整数
• a.length <= 100000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

结果集中的任何一个元素 = 其左边所有的元素乘积 * 其右边所有元素的乘积，故可以这样：

一共遍历a数组两次，一次正向遍历，一次逆向遍历。

• 正向遍历：创建辅助数组bb，其中left[i] = a[0] * a[1] ...* a[i-1] = left[i-1] * a[i-1]，例如[1,2,3,4,5,6]，left[2] = 1 * 2，left[3] = 1* 2 * 3 = left[2] * a[2]
• 逆向遍历：当遍历至下标 i 时，right[i] = a[i+1] * a[i+2]... * a[n-1] = right[i+1] * a[i+1]，例如[1,2,3,4,5,6]，right[3] = 5 * 6，right[2] = 4* 5 * 6 = right[3] * a[3]

最后将b[i] = 正向遍历的结果  * 逆向遍历的结果，即b[i] = left[i] * right[i]。

代码：

 1 class Solution {
 2     public int[] constructArr(int[] a) {
 3         int len = a.length;
 4         if ((len == 0) || a == null) return new int[0];
 5         int[] b = new int[len];
 6         int[] left = new int[len];
 7         //初始化a[0]左边的乘积为1
 8         left[0] = 1;
 9         for (int i = 1; i < len; i++){
10             left[i] = left[i-1] * a[i-1];
11         }
12         int[] right = new int[len];
13         //初始化a[len-1]右边的乘积为1
14         right[len - 1] = 1;
15         for (int i = len - 2; i >= 0; i--){
16             right[i] = right[i+1] * a[i+1];
17         }
18         for(int i = 0; i < len; i++){
19             b[i] = left[i] * right[i];
20         }
21         return b;
22     }
23 }

参考：k神评论区各位老师的题解