[Java][Leetcode middle] 238. 除自身以外数组的乘积

第一个想法是：

想求出所有元素乘积，然后除以i对应的元素本书；这个想法是完全错误的：

1. nums[I] 可能有0
2. 题目要求了不能用除法

第二个想法是：

其实写之前就知道会超时，但是我什么都做不到啊！
双重循环，O(n²)

第三个做法： 借助辅助数组，官方题解

借助辅助数组：使用L[i],R[i]，分别记录i左边和右边元素的乘积
那么res[I]，就是L[I]*R[i]

public int[] productExceptSelf2(int[] nums) {int len = nums.length;int[] result = new int[len];int[] R = new int[len]; //  the right of i: multiplyint[] L = new int[len]; // the left of i: multiplyL[0] = 1;R[len - 1] = 1;for (int i = 1; i < len; i++) {L[i] = L[i - 1] * nums[i - 1];}for (int i = len - 2; i >= 0; i--) {R[i] = R[i + 1] * nums[i + 1];}for (int i = 0; i < len; i++) {result[i] = L[i] * R[i];}return result;}
}

做法四：先用result[]代替上文的L[]

    public int[] productExceptSelf3(int[] nums) {int len = nums.length;int[] result = new int[len];result[0] = 1;for (int i = 1; i < len; i++) {result[i] = result[i - 1] * nums[i - 1];}int R = 1;for(int i = len-1 ; i >= 0 ; i--) {result[i] = R * result[i];R *= nums[i];}return result;}