题目描述

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

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

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

示例 1:

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

具体可见题目详解。

算法思路

这个题目我在备考蓝桥杯时也做过，我记得当时真的很难想出来怎么用O(n)的时间复杂度做，最终好像是看题解才做出来，但是这次做的时候却感觉很简单（可能是还有印象？）大体思路如下：

  1. 分别开辟两个数组记录前缀积和后缀积，所谓前缀积pre[n]就是指对于一个数组nums，nums[0]~nums[n]的乘积。和前缀和比较相像。

  2. 除去元素nums[i]自身，那么整个数组的乘积肯定是$nums[0] \times nums[1] \times … \times nums[i-1] \times nums[i + 1] \times … \times nums[n]$，也就是i的前缀积和后缀积的乘积。

根据以上思路，给出代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> premul(n + 1);
        vector<int> backmul(n + 1);
        premul[0] = 1;
        backmul[n] = 1;
        for (int i = 1; i <= n; i++) {
            premul[i] = nums[i - 1] * premul[i - 1];
            backmul[n - i] = nums[n - i] * backmul[n - i + 1];
        }
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            ans[i] = premul[i] * backmul[i + 1];
        }
        return ans;
    }
};

时间复杂度是O(n)，空间复杂度是O(n)，用到了两个额外数组（不包含结果数组）。运行结果如下：

截屏2025-02-03 12.59.21

但是题目要求是O(1)空间复杂度，这一点我还是没实现，就问了一下copilot，给出的解法思路是一样的，关键在于使用O(1)额外空间，直接在输出数组上操作。并不需要使用额外的前缀积数组和后缀积数组，比较容易理解，具体可以看这个代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 1);
        
        // 从左到右累积乘积
        for (int i = 1; i < n; i++) {
            ans[i] = ans[i-1] * nums[i-1];
        }
        
        // 从右到左累积并与之前结果相乘
        int rightProduct = 1;
        for (int i = n-1; i >= 0; i--) {
            ans[i] *= rightProduct;
            rightProduct *= nums[i];
        }
        
        return ans;
    }
};

除去答案数组以外，没有用到任何容器，因此空间复杂度是O(1)。还是非常聪明的……