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

2025-03-06 约 200 字预计阅读 1 分钟

题目

思路

看题第一眼想到的是先计算给定数组所有元素的乘积，然后对数组中的每个元素 $x$，将总的乘积除以 $x$ 来求得除自身值的以外数组的乘积。但当数组中出现$0$时，这个方法就失效了，且题目说明了不能使用除法。

不能使用除法，又怎么计算除自身值以外数组的乘积呢？考虑到 该数对应的乘积 =其左边的乘积 * 其右边的乘积。所以，可以通过两次遍历依次计算每个数的左右乘积即可得到答案。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        vector<int> ans;

        // 计算每个数的左侧乘积
        for(int i = 0; i < nums.size(); ++i)
        {
            if(i == 0)
            {
                ans.push_back(1);
            }
            else
            {
                ans.push_back(ans[i - 1] * nums[i - 1]);
            }
        }

        // 计算每个数的右侧乘积, 并直接计算答案
        for(int rc = 1, i = nums.size() - 1; i >= 0; --i)
        {
            if(i != (nums.size() - 1))
            {
                rc *= nums[i + 1];
            }

            ans[i] *= rc;
        }

        return ans;
    }
};