题目
Given an array of n integers where n > 1, nums,
return an array output such that output[i] is equal to
the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
解析
给定一个整数数组，求每个位置上，除了这个位置上的数的其他数的乘积。
第一遍就AC且是discuss中最高票答案还是很开心的，这一题要求不用除法且O(n)时间复杂度，让我想到了前两天看的动态规划中的前向和后向思想：
分两次遍历：
第一次从左到右遍历，得到某个位置上所有左边数的乘积（前向）
第二次从右到左遍历，得到某个位置上所有右边数的乘积（后向）
二者一乘即为结果。
基于这种思想，可以用一个数组output保存前向的结果，再用一个变量保存按位后向的结果，每扫描一位就更新output对应位置上的值。当然扫描的第一位的值为1。
代码
public int[] productExceptSelf(int[] nums) {
int[] output = new int[nums.length];
output[0] = 1;
//计算前向乘积
for(int i = 1; i < nums.length; ++i){
output[i] = output[i - 1] * nums[i - 1];
}
//计算后向乘积
int k = 1;
for(int i = nums.length - 1; i >= 0; --i){
output[i] *= k;
k = k * nums[i];
}
return output;
}