11.除了自身以外数组的乘积
题目描述：给你一个整数数组nums，返回 数组answer，其中answer[i]等于nums中除了nums[i]之外其余各元素的乘积 。
题目数据 保证 数组nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在O(n)时间复杂度内完成此题。
思路：
我一开始的想法是先把这个数组所有的乘积算出来，再循环用这个总成绩分别除以每个数组元素的值，这样子只用遍历两次即可成功，但是违反了题目不能用除法的要求。
所以我想到了利用三个数组分别存储每个元素的前缀积，后缀积和结果，结果数组每个元素分别是前一个元素的前缀积和后一个元素的后缀积，虽然是要遍历三次，但是空间复杂度也上升到了O（n），代码如下。
public int[] productExceptSelf(int[] nums) { int len = nums.length; int i; int qian = 0 , hou = len - 1; int qiansum = 1; int housum = 1; int[] result = new int[len]; int[] qiansums = new int[len]; int[] housums = new int[len]; for(i=0;i<len;i++){ qiansum *= nums[i]; qiansums[i] = qiansum; } for(i=len-1;i>=0;i--){ housum *= nums[i]; housums[i] = housum; } for(i=0;i<len;i++){ if(i==0){ result[i] = housums[i+1]; } else if(i==len-1){ result[i] = qiansums[i-1]; } else{ result[i] = housums[i+1] * qiansums[i-1]; } } return result; }后来我一直在想，有没有不需要这几个数组增加空间复杂度的做法，于是我想到了一个，我第一次遍历的时候，把前缀积先存进去，后面我再从尾部向头部遍历一次，利用算出来的后缀积与前面先保存的前缀积相乘，就可以实现题目要求了，于是把空间复杂度降到了O（1），时间复杂度也是O(n)。
public int[] productExceptSelf(int[] nums) { int len = nums.length; int sum = 1,i; int[] result = new int[len]; result[0] = 1; //保存前缀积 for(i=1;i<=len-1;i++){ sum *= nums[i-1]; result[i] = sum; } //把乘积清空 sum = 1; //计算后缀积的同时与前缀积相乘，得到结果。 for(i=len-2;i>=0;i--){ sum *= nums[i+1]; result[i] = result[i] * sum; } return result; }
