LeetCode16 - 除了自身以外数组的乘积

📝 题目描述

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

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

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

示例：


示例 1:

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

示例 2:

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

提示：

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
输入保证数组 answer[i] 在 32 位整数范围内

💡 解题思路

方法一：左右乘积列表

最容易想到的方法，首先构建两个数组 prefix 和 suffix。
其中 prefix[i] 代表输入数组中 nums[i] 前面所有数字的乘积（不含nums[i]自己）；同理，suffix[i] 代表输入数组中 nums[i] 后面所有数字的乘积（不含nums[i]自己）。

值得注意的是，由于 nums[0]前面没有元素，prefix[0] 要置 1；同理，nums[n - 1]后面没有元素，suffix[0] 要置 1。

这样一来，答案数组 answer[i] 就等于 prefix[i] * suffix[i]。

方法二：优化解法

这里可以优化的地方是空间复杂度方面，可以用一个临时变量记录前缀积，然后将 suffix 数组藏进 answer中，节省空间复杂度到 $O(1)$ 。

🔧 代码实现

1、左右乘积列表

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix(n, 0), suffix(n, 0), answer(n);

        // 构建前缀数组
        prefix[0] = 1;
        for(int i = 1; i < n; i++){
            prefix[i] = prefix[i - 1] * nums[i - 1];
        }

        // 构建后缀数组
        suffix[n - 1] = 1;
        for(int i = n - 2; i >= 0; i--){
            suffix[i] = suffix[i + 1] * nums[i + 1];
        }

        // 得出答案
        for(int i = 0; i < n; i++){
            answer[i] = prefix[i] * suffix[i];
        }
        return answer;
    }
};

2、优化解法

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size(), prefix = 1;
        vector<int> answer(n);

        // 利用answer数组构建后缀积
        answer[n - 1] = 1;
        for(int i = n - 2; i >= 0; i--){
            answer[i] = answer[i + 1] * nums[i + 1];
        }

        // 得到答案
        for(int i = 0; i < n; i++){
            answer[i] = prefix * answer[i];
            prefix *= nums[i];
        }

        return answer;
    }
};

📊 复杂度分析

1、左右乘积列表

时间复杂度： $O(N)$ ，其中 $N$ 指的是数组 nums 的大小。预处理 prefix 和 suffix 数组以及最后的遍历计算都是 $O(N)$ 的时间复杂度。
空间复杂度： $O(N)$ ，其中 $N$ 指的是数组 nums 的大小。使用了 prefix 和 suffix 数组去构造答案，prefix 和 suffix 数组的长度为数组 nums 的大小。

2、优化解法

时间复杂度： $O(N)$ ，其中 N 指的是数组 nums 的大小。分析与方法一相同。
空间复杂度： $O(1)$ ，输出数组不算进空间复杂度中，因此我们只需要常数的空间存放变量。

🎯 总结

核心思想：稍微记一下优化解法。