中等 · 普通数组 · 原题

题目信息

LeetCode #238 · Product of Array Except Self

标签：数组、前缀和

题目要求

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

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

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

示例 1:

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

示例 2:

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

提示：

  • 2 <= nums.length <= 10^5

  • -30 <= nums[i] <= 30

  • 输入 保证 数组 answer[i] 在 32 位 整数范围内

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

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> left(nums);
        vector<int> right(nums);
        vector<int> ans(nums);
        for(int i=1;i<nums.size();i++){
            left[i]=left[i-1]*left[i];
        }
        for(int j=nums.size()-2;j>=0;j--){
            right[j]=right[j+1]*right[j];
        }
        ans[0]=right[1];
        ans[ans.size()-1]=left[left.size()-2];
        for(int i=1;i<nums.size()-1;i++){
            ans[i]=left[i-1]*right[i+1];
        }
        return ans;
    }
};

//不使用额外空间
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ans(nums.size());
        ans.back()=1;
        for(int i=nums.size()-2;i>=0;i--){
            ans[i]=ans[i+1]*nums[i+1];
        }
        int pre=1;
        for(int i=0;i<nums.size();i++){
            ans[i]*=pre;
            pre*=nums[i];
        }
        return ans;
    }
};

返回目录