LeetCode OJ 238. Product of Array Except Self 解题报告

    题目链接：https://leetcode.com/problems/product-of-array-except-self/

Discuss

    给出一个数组，要求计算一个新数组，数组里所有的元素都是除了自己以外的元素乘积。并且要求不许用除法。

    《编程之美》上的一道原题。创建两个辅助数组，一个保存所有左边元素乘积的结果。一个保存所有右边元素乘积的结果。借助这两个数组，一次遍历就可以得到结果。

    我的AC代码

public class ProductofArrayExceptSelf {
 
	public static void main(String[] args) {
		int[] a = { 1, 2, 3, 4 };
		System.out.print(Arrays.toString((productExceptSelf(a))));
	}
 
	public static int[] productExceptSelf(int[] nums) {
		int len = nums.length;
		int[] r = new int[len];
 
		int[] left = new int[len];
		int[] right = new int[len];
		left[0] = nums[0];
		for (int i = 1; i < len; i++) {
			left[i] = left[i - 1] * nums[i];
		}
		right[len - 1] = nums[len - 1];
		for (int i = len - 2; i >= 0; i--) {
			right[i] = right[i + 1] * nums[i];
		}
 
		r[0] = right[1];
		r[len - 1] = left[len - 2];
		for (int i = 1; i < len - 1; i++) {
			r[i] = left[i - 1] * right[i + 1];
		}
		return r;
	}
}