原题链接
class Solution {
/**
* 动态规划
* left[i] 为 a[i] 左边元素的乘积 (不包含 a[i])
* right[i] 为 a[i] 右边元素的乘积 (不包含 a[i])
* 则结果 res[i] = left[i] * right[i]
*
* @param a
* @return
*/
public int[] constructArr(int[] a) {
int len = a.length;
int[] left = new int[len];
if (len <= 1) return left;
int[] right = new int[len];
left[0] = 1;
for(int i = 1; i < len; i++){
left[i] = left[i - 1] * a[i - 1];
}
right[len - 1] = 1;
for(int i = len - 2; i >= 0; i--){
right[i] = right[i + 1] * a[i + 1];
left[i] *= right[i];
}
return left;
}
}