剑指 Offer 66. 构建乘积数组--数组

用两个数组维护，然后想要得到下面这样的两个数组，left表示a[i]左边的，right表示a[i]右边的
left： 1，a[0]，a[0]*a[1]，a[0]*a[1]*a[2]
right： a[0]*a[1]*a[2]，a[1]*a[2]，a[2]，1

可以推理出这两个数组是如何构建
left[0] = 1
left[i] = left[i - 1] *a[i - 1]

right[len - 1] = 1
right[i] = right[i + 1] * a[i + 1]

最后将这两个数组遍历求积即可

class Solution {
    public int[] constructArr(int[] a) {
        if (a == null || a.length == 0) return a;
        int len = a.length;
        int[] left = new int[len];
        int[] right = new int[len];
        left[0] = right[len - 1] = 1;

        for (int i = 1; i < len; i++) {
            left[i] = left[i - 1] * a[i - 1];
        }
        for (int i = len - 2; i >= 0; i--) {
            right[i] = right[i + 1] * a[i + 1];
        }

        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            ans[i] = left[i] * right[i];
        }
        return ans;
    }
}