思路：动态规划
对于数组B中元素B[i]，它的值等于A数组中 i 左侧元素乘积，与 i 右侧元素乘积 的乘积
画表可知：
| B[1]= | 1* | A[2]* | A[3]* | A[4] |
| B[2]= | A[1]* | 1* | A[3]* | A[4] |
| B[3]= | A[1]* | A[2]* | 1* | A[4] |
| B[4]= | A[1]* | A[2]* | A[3]* | 1 |
因此需要维护两个 dp 数组 left、right，left 记录 i 左侧元素乘积，right 记录 i 右侧元素乘积
结果B[ i ] = left[ i ] * right [ i ]
代码：
时间复杂度O（n），空间复杂度O（n）
class Solution { public int[] constructArr(int[] a) { if (a == null || a.length == 0) return a; int[] left = new int[a.length]; int[] right = new int[a.length]; int[] ans = new int[a.length]; left[0] = 1; right[a.length-1] = 1; for (int i = 1; i < a.length; i++) { left[i] = left[i-1] * a[i-1]; } for (int i = a.length-2; i >= 0; i--) { right[i] = right[i+1] * a[i+1]; ans[i] = left[i] * right[i]; } ans[a.length-1] = left[a.length-1]; return ans; } }
原文：https://www.cnblogs.com/zccfrancis/p/14459906.html