求除自身外的乘积

求除自身外的乘积

题目

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

题解

一开始的想法是遍历，发现超时

使用迭代法分别求出一个位置左边的数的乘积，和，右边的乘积

class Solution {
    public int[] productExceptSelf(int[] nums) {
    //    int  a []=new int[nums.length];
    //     for(int i=0;i<nums.length;i++){
    //         int  sum=1;
    //         for(int j=0;j<nums.length;j++){
    //             if(i!=j){
    //                 sum*=nums[j];
    //             }
    //         }
    //         a[i]=sum;
    //     }
    //     return a;
        int L[]=new int [nums.length];
        int R[]=new int [nums.length];
        int a[]=new int [nums.length];
        L[0]=1;
        R[nums.length-1]=1;
        for(int i=1;i<nums.length;i++){
            L[i]=L[i-1]*nums[i-1];
        }
        for(int j=nums.length-2;j>=0;j--){
            R[j]=R[j+1]*nums[j+1];
        }
        for(int i=0;i<nums.length;i++){
            a[i]=L[i]*R[i];
        }
        return a;
    }
}