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

【练习】力扣热题100 除自身以外数组的乘积

article 2025/1/15 21:26:36

题目

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

来源：力扣热题100 除自身以外数组的乘积

题解

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> a(n, 1);

        // 计算前缀积
        for (int i = 1; i < n; i++) {
            a[i] = a[i - 1] * nums[i - 1];
        }

        // 计算后缀积并更新结果
        int t = 1;
        for (int i = n - 1; i >= 0; i--) {
            a[i] *= t;
            t *= nums[i];
        }

        return a;
    }
};

计算除自身以外数组的乘积。它的目标是给定一个整数数组 nums，返回一个数组 a，其中 a[i] 是 nums 中除 nums[i] 之外所有元素的乘积。要求时间复杂度为 O(n)，并且不能使用除法。

以下是代码的详细分析：

代码逻辑分析：

初始化结果数组 a：
```
vector<int> a(n, 1);
```
- 创建一个大小为 n 的数组 a，并初始化为 1。这个数组将用于存储最终结果。
计算前缀积：
```
for (int i = 1; i < n; i++) {
    a[i] = a[i - 1] * nums[i - 1];
}
```
- 从左到右遍历数组，计算每个位置左侧所有元素的乘积，并存储在 a 中。
- 例如，a[i] 表示 nums[0] * nums[1] * ... * nums[i-1]。
- 这一步完成后，a 数组存储了每个位置左侧的乘积。
计算后缀积并更新结果：
```
int t = 1;  // 初始化后缀积为 1
for (int i = n - 1; i >= 0; i--) {
    a[i] *= t;  // 将后缀积乘到 a[i] 上
    t *= nums[i];  // 更新后缀积
}
```
- 从右到左遍历数组，使用变量 t 累乘右侧元素，并将结果乘到 a[i] 上。
- 例如，a[i] 最终等于 a[i] * (nums[i+1] * nums[i+2] * ... * nums[n-1])。
- 这一步完成后，a 数组中的每个元素就是除自身外所有元素的乘积。

举例说明：

假设输入数组为 nums = [1, 2, 3, 4]，运行过程如下：

初始化：
- a = [1, 1, 1, 1]。
计算前缀积：
- i = 1：a[1] = a[0] * nums[0] = 1 * 1 = 1。
- i = 2：a[2] = a[1] * nums[1] = 1 * 2 = 2。
- i = 3：a[3] = a[2] * nums[2] = 2 * 3 = 6。
- 此时 a = [1, 1, 2, 6]。
计算后缀积并更新结果：
- 初始化 t = 1。
- i = 3：a[3] *= 1 = 6 * 1 = 6，t = 1 * 4 = 4。
- i = 2：a[2] *= 4 = 2 * 4 = 8，t = 4 * 3 = 12。
- i = 1：a[1] *= 12 = 1 * 12 = 12，t = 12 * 2 = 24。
- i = 0：a[0] *= 24 = 1 * 24 = 24，t = 24 * 1 = 24。
- 最终 a = [24, 12, 8, 6]。