题解 | 构建乘积数组

• left[i]表示原数组第i个元素以左(<i)的所有元素的累积
• right[i]表示原数组第i个元素以右(>i)的所有元素的累积
• 需要注意的是left数组的第一个元素和right数组的最后一个元素都是1
• 题目限定了输入范围因此不用特殊考虑输入校验问题

public class Solution {
    public int[] multiply(int[] a) {
        int[] left = new int[a.length];
        int[] right = 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];
        }

        int[] ret = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            ret[i] = left[i] * right[i];
        }
        return ret;
    }
}