【Leetcode每日一题】 前缀和 - 除自身以外数组的乘积（难度⭐⭐）（27）

1. 题目解析

题目链接：238. 除自身以外数组的乘积

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

核心在于计算题目所给数组除本身外其他元素的积的数组返回即可。

2. 算法原理

为了计算每个位置i的最终结果ret[i]，我们需要考虑两部分：

1. nums[0] * nums[1] * nums[2] * ... * nums[i - 1]，表示位置i之前的所有元素的乘积。
2. nums[i + 1] * nums[i + 2] * ... * nums[n - 1]，表示位置i之后的所有元素的乘积。

为了高效计算，我们可以利用前缀和的概念，构建两个辅助数组：post和suf。

• post数组：存储每个位置i之前的所有元素的乘积，即[0, i - 1]区间内元素的累积乘积。
• suf数组：存储每个位置i之后的所有元素的乘积，即[i + 1, n - 1]区间内元素的累积乘积。

通过预先计算post和suf数组，我们可以快速得到每个位置i的最终结果ret[i]，即ret[i] = post[i] * suf[i]。这样，我们就能够高效地处理所有位置的结果。

3. 代码编写 

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n), g(n);
        f[0] = g[n - 1] = 1;
        for(int i = 1; i < n; i++)
            f[i] = f[i - 1] * nums[i - 1];
        for(int i = n - 2; i >= 0; i--)
            g[i] = g[i + 1] * nums[i + 1];
        vector<int> ret(n);
        for(int i = 0; i < n; i++)
            ret[i] = f[i] * g[i];
        return ret;
    }
};

The Last

嗯，就是这样啦，文章到这里就结束啦，真心感谢你花时间来读。

觉得有点收获的话，不妨给我点个赞吧！

如果发现文章有啥漏洞或错误的地方，欢迎私信我或者在评论里提醒一声~