题目大意：
除自身以外数组的乘积
给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入:[1,2,3,4]输出:[24,12,8,6]
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=238
解题思路分析：
本题最初想到的思路是先得到所有数的乘积，然后在计算每个数字左右两侧所有数乘积时，用总的乘积除以自身即可。但本题明确要求不能使用除法，所以该解法不可行，另外这种解法也存在一个漏洞，如果数组中存在0，那么该解法就无能为力了。比如[5,0,8]，所有数字乘积为0，虽然对于5和8没影响，但数字0，首先它自身无法作为除数，另外，其它数的乘积我们也无从获知。
所以本题需要使用到前缀乘积的方式来解题，这个思路非常类似之前多次介绍过的前缀和数组思路。我们维护两个数组，事先求出每一位数字左边所有数的乘积（前缀乘积），以及右边所有数的乘积（后缀乘积），然后对于当前位，左边乘积乘以右边乘积即是当前答案。
另外，本题要求除了返回结果外，只能使用常量级别的内存空间，即空间复杂度要求在O(1)，因此，我们可以使用返回结果的数组临时作为前缀乘积数组，后缀乘积我们使用一个变量来迭代即可。
实现代码：
public int[] productExceptSelf(int[] nums) {
// 返回结果
int[] res = new int[nums.length];
// 现将返回结果数组作为前缀乘积数组
// 第0位左边没有数字，因此它左边数字乘积为1
res[0]=1;
// 计算每一位的前缀乘积
for(int i=1;i<nums.length;i++){
// 当前位的前缀乘积等于前一位前缀乘积乘以前一位数字
res[i]=res[i-1]*nums[i-1];
}
// 动态迭代结算后缀乘积，最后一位不存在右侧数字，
// 后缀乘积为1
int leftProduct =1;
// 从最后一位循环数组
for(int i=nums.length-1;i>=0;i--){
// 计算每一位的后缀乘积
leftProduct*= i<nums.length-1?nums[i+1]:1;
// 当前位的前缀乘积乘以后缀乘积即是当前位答案
res[i]*=leftProduct;
}
return res;
}本题解法执行时间为1ms。
Runtime: 1 ms, faster than 100.00% of Java online submissions for Product of Array Except Self.
Memory Usage: 47.7 MB, less than 5.51% of Java online submissions for Product of Array Except Self.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-238-product-of-array-except-self-解题思路分析/