productOfArrayExceptSelf

238. 除自身以外数组的乘积

分析

前缀积数组 pre：
- pre[i] 表示 nums[0] 到 nums[i - 1] 的乘积
- 用于保存当前元素之前所有元素的乘积
后缀积变量 sub：
- 在第二次遍历时，通过一个变量动态记录从右到左的乘积（即 nums[i + 1] 到 nums[n - 1]的乘积）
- 每次更新 pre[i] 为 pre[i] * sub（计算结果数组），并更新 sub

时间复杂度

前缀积遍历一次，后缀积遍历一次，总体复杂度为 O(n)

空间复杂度

使用了一个前缀积数组和一个后缀积变量，空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


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

        // 初始化前缀积数组
        std::vector<int> pre(n, 1);
        for (int i = 1; i < n; ++ i)
            pre[i] = pre[i - 1] * nums[i - 1];

        // 动态计算后缀积并更新结果
        int sub = 1;
        for (int i = n - 1; i >= 0; -- i)
        {
            pre[i] *= sub;
            sub *= nums[i];
        }

        return pre;
    }
};