思路
一开始想到的是按位乘
看了题解，思路是存i左边的乘积和 与 i右边的乘积和
代码一：
需要三次循环,需要额外空间 left和right数组
代码：
public int[] productExceptSelf(int[] nums) {int[] left = new int[nums.length];int[] right = new int[nums.length];int[] result = new int[nums.length];left[0] = nums[0];for (int i = 1; i < nums.length; i++) {left[i] = left[i-1]*nums[i];}right[nums.length-1] = nums[nums.length-1];for (int i = nums.length-2; i >=0; i--) {right[i] = right[i+1]*nums[i];}// 计算两个特殊值，左边界和右边界，题目说明数组长度大于1result[0] = right[1];result[nums.length-1] = left[nums.length-2];for (int i= 1;i<nums.length-1;i++){result[i]= left[i-1] * right[i+1];}return result;}
复杂度
代码二 不需要额外数组
public int[] productExceptSelf(int[] nums) {int[] result = new int[nums.length];int right =1;result[0] = nums[0];//用result 充当之前的left，计算左边的乘积for (int i = 1; i < nums.length; i++) {result[i] = result[i-1]*nums[i];}
// 从右边开始计算真正的result，计算到index=1,index=0单独计算for (int i = nums.length-1; i >0 ; i--) {result[i] = result[i-1] * right;right = right * nums[i];//right一直更新，记录右边的乘积}result[0] = right;return result;}}
代码三：一次循环
public int[] productExceptSelf(int[] nums) {int[] result = new int[nums.length];Arrays.fill(result,1);int left = 1;int right = 1;for (int i = 0; i <nums.length; i++) {result[i] = result[i] * left; //从左到右计算 自己左边的乘积result[nums.length-1-i] = result[nums.length-1-i]* right;//从右到左计算 自己右边的乘积left = left * nums[i]; //记录左边的乘积right = right * nums[nums.length-1-i];//记录右边的乘积}return result;}}
主要是下面的循环
result[i] = result[i] * left;
一开始result数组都是赋值1，所以在左右两个指针没有交叉的时候，
result[i] = left
result[nums.length-1-i] = right
left是i左边的乘积（不包括i）
right是i右边的乘积（不包括i）
当左右两个指针交叉以后，
result[i] = result[i] * left;，此时的result[i]则不是1，而是之前计算的一边的值。
这个思路很难想到
