当前位置：首页 > article >正文

力扣HOT100之普通数组：238. 除自身以外数组的乘积

article 2025/4/2 8:58:48

这道题不能使用除法，我第一时间想到用前缀表和后缀表来解决，假设数组nums的长度为n，我们直接定义前缀表pre和后缀表suf，其中pre[i] = pre[i - 1] * nums[i - 1] = nums[0] * nums[1] * ... * nums[i - 1] ，而suf[j] = suf[j + 1] * nums[j + 1] = nums[n - 1] * nums[n - 2] * ... * nums[j + 1] ，所以返回的向量result中，result[i] = pre[i] * suf[i]，其中特别要注意的是，前缀表pre的长度为n ，pre[0] = 1，而后缀表的长度为n，suf[n - 1] = 1,一共需要三次线性遍历，时间复杂度为O(n)。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> result;
        vector<int> pre(nums.size(), 1);  //前缀乘积
        vector<int> suf(nums.size(), 1);      //后缀乘积
        for(int i = 1; i < pre.size(); ++i)  //构造前缀乘积表
            pre[i] = pre[i - 1] * nums[i - 1];
        for(int i = suf.size() - 2; i >= 0; --i) //构造后缀乘积表
            suf[i] = suf[i + 1] * nums[i + 1];
        for(int i = 0; i < nums.size(); ++i)
            result.emplace_back(pre[i] * suf[i]);
        return result;
    }
};