[刷题技巧] LeetCode238. 除自身以外数组的乘积

题目描述

思路：前缀/后缀乘积数组

构造除自身以外数组的左边前缀乘积
构造除自身以外数组的右边后缀乘积
然后对应位置相乘

方法一：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        // 前缀乘积数组: leftProduct[i]表示索引i左侧所有元素的乘积
        int[] leftProduct = new int[n];
        leftProduct[0] = 1;
        for (int i = 1; i < n; i ++) {
            leftProduct[i] = leftProduct[i - 1] * nums[i - 1];
        }
        // 后缀乘积数组：rightProduct[i]表示索引i右侧所有元素的乘积
        int[] rightProduct = new int[n];
        rightProduct[n - 1] = 1;
        for (int i = n - 2; i >= 0; i --) {
            rightProduct[i] = rightProduct[i + 1] * nums[i + 1];
        }
        // 对应位置相乘
        int[] res = new int[n];
        for (int i = 0; i < n; i ++) {
            res[i] = leftProduct[i] * rightProduct[i];
        }
        return res;
    }
}

时间复杂度：O(n)
额外空间复杂度：O(n)

方法二：优化方法一

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        res[0] = 1;
        // res[i]表示索引i左侧所有元素的乘积
        for (int i = 1; i < n; i ++) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        // 每个元素的右边所有元素的乘积存储在一个变量中
        int rightProduct = 1;
        for (int i = n - 1; i >= 0; i --) {
            // 对于索引i左边的乘积为res[i],右边的乘积为rightProduct
            res[i] = res[i] * rightProduct;
            // 更新右边乘积
            rightProduct = rightProduct * nums[i];
        }
        return res;
    }
}

在方法一的基础上进行优化：

• 将res用于记录left数组
• 然后用一个变量维护right数组

时间复杂度：O(n)
额外空间复杂度：O(1)