力扣面试经典150题之238：除了自身以外数组的乘积

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