LeetCode 238 计算数组除自己外的元素乘积

最新推荐文章于 2025-03-30 14:46:11 发布

missing_2009

最新推荐文章于 2025-03-30 14:46:11 发布

阅读量604

点赞数

分类专栏： Leetcode

本文链接：https://blog.csdn.net/missing_2009/article/details/59104360

版权

Leetcode 专栏收录该内容

3 篇文章

订阅专栏

本文介绍了一种不使用除法计算数组中每个元素的乘积，除了自身位置外的所有其他元素的乘积的方法。该算法避免了直接相除可能出现的除数为零的问题，并通过两遍扫描确保了O(n)的时间复杂度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 1); // res有n个元素，值为1
        if(n <= 1){
            return nums;
        }
        for(int i = 1; i < n; i++){ // res={1, n0, n0n1, n0n1n2};
            res[i] = res[i-1] * nums[i-1];
        }
        int right = 1;
        for(int i = n-2; i >= 0; i--){
            right *= nums[i+1]; // right = n3,n3n2,n3n2n1
            res[i] = res[i]*right;
        }
        return res;
    }
};