leetcode 238. 除自身以外数组的乘积（优质解法）

代码：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length =nums.length;
        int[] f=new int[length];    //前缀积数组
        int[] g=new int[length];   //后缀积数组

        f[0]=g[length-1]=1; //  去除边界值

        //填充前缀和后缀积数组
        for(int i=1;i<length;i++){
            f[i]=f[i-1]*nums[i-1];
        }

        for(int i=length-2;i>=0;i--){
            g[i]=g[i+1]*nums[i+1];
        }

        int[]results=new int[length];
        for(int i=0;i<length;i++){
            results[i]=f[i]*g[i];
        }

        return results;
    }
}

题解：

? ? ? ? 本题的题意描述得很清晰，我们要计算?nums 数组中每个下标除自身以外数组的乘积，对于 nums=【1，2，3，4】，result[ 1 ] = 1*3*4 = 12,

? ? ? ? 我们可以很简单的想到一个暴力解法，就是和题意一样，直接计算每个下标除自身以外数组的乘积，那么我们每计算一个下标对应的值就需要遍历一次数组，要计算 n 个下标，所以需要遍历 n 次，时间复杂度就为：O（n^2）,这是很大的复杂度，我们需要进行优化

? ? ? ? 由于计算某个下标除自身以外数组的乘积,需要把下标之前和之后的数据都乘起来，我们可以先单独计算下标之前的数据乘积，再计算下标之后的数据乘积，再将得到的两个数据相乘，也能达到对应的效果，所以我们这里的解题可以用到前缀和的思想

? ? ? ? 为了方便理解，我画了如下的图：

? ? ? ? 如上图，要想获得 f[ i ]，即 i 下标的前缀积，可以先获得 i - 1 下标的前缀积，再乘以 nums[ i -1] ,我们得到推导式：f[ i ] = f[ i-1 ] * nums[ i-1 ]

? ? ? ? 要想获得 g[ i ]，即 i 下标的后缀积，可以先获得 i + 1 下标的后缀积，再乘以 nums[ i +1] ,我们得到推导式：g[ i ] = g[ i+1 ] * nums[ i+1 ]

? ? ? ? 根据上面的推导式填充前缀积数组 f 和后缀积数组 g 即可，填充完以后，i 下标的结果 result[ i ] = f [ i ] * g[ i ]?

? ? ? ? 但其中有一个细节需要注意，在填充数组 f 时，当 i =0 ，会出现 -1 这个越界下标，所以我们需要提前初始化，当下标为 0 时，前缀积为 1，同理，在填充数组 g 时，当 i =nums.length -1??，会出现 nums.length 这个越界下标，所以我们需要提前初始化，当下标为 nums.length?时，后缀积为 1

????????

????????