Leetcode学习之238. 除自身以外数组的乘积_除自己以外的乘积递归算法

逐个计算，如果可以除法，只需要遍历一次得出整个数组的乘积，然后第二次遍历的时候，用总乘积除掉当前idx对应val即可。但是题目禁止了…

因此我们可以利用乘法，其实题目就需要把除去该数，其他的所有乘积，我们只需要遍历一遍，把该数组每个对应的数据项的左右乘数算出来即可，

步骤如下：
1. 新建左右前缀数组，用于存放当前idx所对应的数据的左右乘数

		int len = nums.length;
        int[] res = new int[len], L= new int[len],R = new int[len];
1
2

2. 边界处理位置，比如num[0]和nums[max]他们左/右前缀的乘积只能是1，因为没有乘数相乘，用 “1” 不影响结果

		L[0] =1;R[len-1] = 1;
1

3. L[i] = L[i-1]*nums[i-1]，R[i] =R[i+1]*nums[i+1]

		//从第2个数开始遍历,填充L左前缀数组
		for (int i = 1;i<len;i++){
            L[i] = L[i-1]*nums[i-1];
        }
        //从倒数2个数开始遍历,填充L左前缀数组
        for (int j = len-2;j>=0;j--){
            R[j] = R[j+1]*nums[j+1];
        }
1
2
3
4
5
6
7
8

4. 对于res数组，只需要把num[i]的L[i]*R[i]即可

		for(int z = 0;z<len;z++){
            res[z] = L[z]*R[z];
        }
1
2
3