【LeetCode-中等】238. 除自身以外数组的乘积（详解）

题目

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/product-of-array-except-self

方法1：左右数组

乘积 = 当前数左边的乘积 * 当前数右边的乘积

用left数组存储：left[i]表示从左侧下标为0 一直连续乘到i的结果

用right数组存储：right[i]表示从右侧下标为n-1 一直连续乘到i的结果

answer[i] = left[i-1] * right[i+1]

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int answer[] = new int[n];
        //left[i]表示从左侧下标为0 一直连续乘到i的结果
        int left[] = new int[n];
        //right[i]表示从右侧下标为n-1 一直连续乘到i的结果
        int right[] = new int[n];
        //初始化left 和 right
        left[0] = nums[0];
        right[n-1] = nums[n-1];
        //给 left数组赋值
        for (int i = 1; i < n; i++) {
            left[i] = left[i-1] * nums[i];
        }
        //给 right数组赋值
        for (int i = n-2; i >=0 ; i--) {
            right[i] = right[i+1] * nums[i];
        }
        //给answer数组赋值
        for (int i = 0; i < n; i++) {
            if (i==0) {
                answer[i] = right[i+1];
                continue;
            }
            if (i == n-1){
                answer[i] = left[i-1];
                continue;
            }
            answer[i] = left[i-1] * right[i+1];
        }
        return answer;
    }
}

效果不是很好，应该可以优化 

方法2：优化方法1

方法1中我们用了三次for循环，分别给 left 和 right 和 answer 数组赋值，实际上，我们可以在给ringht数组赋值的同时，给answer数组赋值，这样少用一次for循环，时间复杂度会降低。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int answer[] = new int[n];
        //left[i]表示从左侧下标为0 一直连续乘到i的结果
        int left[] = new int[n];
        //right[i]表示从右侧下标为n-1 一直连续乘到i的结果
        int right[] = new int[n];
        //初始化left[0]、right[n-1]
        left[0] = nums[0];
        right[n-1] = nums[n-1];
        //给left数组赋值
        for (int i = 1; i < n; i++) {
            left[i] = left[i-1] * nums[i];
        }
        answer[n-1] = left[n-2];
        //给right数组赋值
        for (int i = n-2; i >=0 ; i--) {
            right[i] = right[i+1] * nums[i];
            if (i==0) {
                answer[i] = right[i+1];
                continue;
            }
            answer[i] = left[i-1] * right[i+1];
        }
        return answer;
    }
}

 

果然，降低了很多，nice，这道题作为一道中等难度的题，还是很好做的