前缀和-238-除自身以外数组的乘积-力扣(LeetCode)

白天的黑夜

发布于 2025-10-22 17:08:20

3120

文章被收录于专栏：leetcode题目解析和知识分享leetcode题目解析和知识分享

一、题目解析

1.answer[i]等于nums[i]中除nums[i]之外其余各元素的乘积

2.前缀元素和后缀的乘积在32位整数范围内(也就是不会超出int，暗示使用前缀和思想)

3.不要使用除法，时间复杂度为O(N)

二、算法原理

解法1：暴力解法

固定一个数i，然后依次计算[0,i-1]，[i+1,n-1]内所有元素的乘积，时间复杂为O(N^2)

解法2：前缀和思想(前缀积)

通过前缀积数组和后缀积数组的预处理，ans[i]=f[i]g[i]；但是我们能发现f[0]和g[n-1]的值是等于1的，举例ans[0]=f[0]g[0]，g[0]表示[1，n-1]内所有元素的积，符合要求，所以f[0]=1;g[n-1]同理

三、代码示例

由于解法1时间复杂度为O(N^2)会超时，所以只展示解法2的代码

解法2：

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