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].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
[思路]：刚看到题时我想到的是用两重循环直接求解，这样实现很简单。
java代码：
public class Solution { public static int[] productExceptSelf(int[] nums) { int [] product=new int[nums.length]; for(int i=0;i<nums.length;i++){ product[i]=1; for(int j=0;j<nums.length;j++){ if(j!=i) product[i]*=nums[j]; } } return product; } ｝
测试结果正确，提交上去毫无意外地超时了。
继续思考，对于一个给定的数组nums[1,2,3,4]，我们用一个res[4]的数组来存放结果，res中存放的数据应是
res[0]=2*3*4
res[1]=1*3*4
res[2]=1*2*4
res[3]=1*2*3
这样我们可以发现一些规律：
1.数组的两端直接就是正确的结果
2.两个数组的中间部分相乘就是正确结果
java代码：
public class Solution { public int[] productExceptSelf(int[] nums) { int[] res=new int[nums.length]; res[res.length-1]=1; for(int i=nums.length-2;i>=0;i--){ res[i]=res[i+1]*nums[i+1]; } int[] right=new int[nums.length]; right[0]=1; for(int i=1;i<nums.length;i++){ right[i]=right[i-1]*nums[i-1]; res[i]*=right[i]; } return res; } }
LeetCode (238):Product of Array Except Self
原文：http://www.cnblogs.com/rever/p/4889381.html