【LC75】No238. 除自身以外数组的乘积

题目描述

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

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

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

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

示例

示例 1:

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

示例 2:

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

链接

思路

依旧是很好理解的题目，没有背景设置，所以中译中环节省略。

题目要求在 O(n) 的时间内完成，即解法中的循环不可以出现嵌套。首先我们可以想到的是先计算出数组所有元素的乘积，再依次除以每个元素，即可得到除自身外的所有元素的乘积。

但题目又要求不能使用除法，同时由于数组元素可能为 0，使用除法会导致异常，所以我们含泪放弃这个方法。

换个角度思考，O(n)的时间复杂度虽然要求循环不能嵌套，但我们可以进行多次遍历。

解法一：分别计算前缀积和后缀积

我们将算法分三次遍历完成：

1. 第一次遍历计算前缀积。从前开始循环，计算 i 元素所有前置元素的乘积，即计算 num[0]…nums[i-1] 的乘积。

2. 第二次遍历计算后缀积。从末尾开始循环，计算 i 元素所有后置元素的乘积，即计算 num[i+1]…nums[len-1] 的乘积。

3. 第三次遍历计算最终结果。从头开始循环，计算 i 元素的前缀积和后缀积的乘积。

最后输出最终结果数组。

代码

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        // 前缀乘积
        int[] left = new int[len];
        // 后缀乘积
        int[] right = new int[len];
        // 结果数组
        int[] ans = new int[len];
        // 第一个元素左边没有元素，因此前缀积数组的第一个元素为1
        left[0] = 1;
        // 计算i所有前缀元素乘积
        for (int i = 1; i < len; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }
        // 最后一个元素右边没有元素，因此后缀积数组的最后一个元素为1
        right[len - 1] = 1;
        // 计算i所有后缀元素乘积
        for (int i = len - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }
        // 计算最终结果，i的前缀乘积和后缀乘积的积
        for (int i = 0; i < len; i++) {
            ans[i] = left[i] * right[i];
        }
        return ans;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)

解法二：解法一の优化

进阶中新增要求，除了返回的结果数组，能否在 O(1) 的空间复杂度内完成解题。

在解法一中，除了结果数组，我们额外使用了两个数组分别记录前缀积和后缀积。

对于进阶要求，我们可以做如下改动：

1. 第一次遍历计算前缀积，直接将结果保存至结果数组 ans 中。

2. 第二次遍历同时计算后缀积与最终结果。使用一个单独的变量 right 存储每一次后缀积的结果，之后更新结果数组。

代码

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] ans = new int[len];
        // 第一个元素左边没有元素，因此前缀积数组的第一个元素为1
        ans[0] = 1;
        // 计算i所有前缀元素乘积
        for (int i = 1; i < len; i++) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }
        // 最后一个元素右边没有元素，因此令后缀积累计值的初始值为1
        int right = 1;
        // 直接计算最终结果
        // 最后一个元素nums[len-1]只存在前置元素，所以此时下标从len-2开始
        for (int i = len - 2; i >= 0; i--) {
            // 计算后缀积，利用right作为累计值
            right = right * nums[i + 1];
            // 计算前缀积和后缀积的乘积，更新结果数组
            ans[i] = ans[i] * right;
        }
        return ans;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)（若去除结果数组 ans 不算，则为 O(1) ）