01—除自身以外数组的乘积【LeetCode238】

题目

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

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

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

来源：力扣（LeetCode ）

示例一：

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例二：

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

解题

思路：

计算除了当前索引中其它所有数的乘积，可以通过计算该索引下的数的左边和右边的乘积之和相乘即可。首先遍历题给数组nums，分别计算题中数组的每个索引的左边的所有数的乘积和右边所有数的乘积，放入两个数组L和R中，然后再新建一个数组result，对数组result进行一次遍历，数组result中每个索引处的值等于数组L R 中两个索引处相乘。最后返回结果数组result。

解决：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] L = new int[nums.length];
        int[] R = new int[nums.length];
        int[] result = new int[nums.length];
        //首先初始化左右两个数组的固定值，L的第一个值为1，R的最后一个值为1
        L[0] = 1;
        R[nums.length-1] = 1;
        //填充L数组，即每个索引处左边的乘积的数组，第一个索引处的值已经设置。
        for(int i=1;i< nums.length;i++){
            L[i] = nums[i-1]*L[i-1];
        }
        //填充R数组，即每个索引处右边的乘积的数组，最后一个索引处的值已经设置。
        for(int i= nums.length-2;i>=0;i--){
            R[i] = nums[i+1] * R[i+1];
        }
        //然后填充result数组
        for(int i=0;i<nums.length;i++){
            result[i] = L[i]*R[i];
        }
        return result;
    }
}