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

Bin大约 3 分钟

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

题目：除自身以外数组的乘积

描述

给定一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

要求：

不允许使用除法。
时间复杂度要求为 O(n)。

示例

示例 1:

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

示例 2:

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

解题思路

核心思想：前缀乘积 + 后缀乘积

对于任意元素 nums[i]，其除自身以外的乘积可以分为两部分：
1. 左侧所有元素的乘积（即前缀积）。
2. 右侧所有元素的乘积（即后缀积）。

例如，对于 nums = [1, 2, 3, 4]：

对于 nums[2] = 3：
- 左侧乘积是 1 * 2。
- 右侧乘积是 4。

最终结果为两部分乘积的积：1 * 2 * 4 = 8。

实现步骤

计算前缀积：
- 使用一个数组 prefix，prefix[i] 表示从 nums[0] 到 nums[i-1] 的乘积。
- 初始化 prefix[0] = 1。
计算后缀积：
- 使用一个变量 suffix 来保存从右侧累积的乘积。
- 直接在结果数组 answer 中更新乘积。
同时计算最终结果：
- 对于每个位置 i，最终结果为：
```
answer[i] = prefix[i] * suffix
```

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        Solution solution = new Solution();
        int[] result = solution.productExceptSelf(nums);

        // 输出结果数组
        System.out.print("[");
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]);
            if (i < result.length - 1) System.out.print(",");
        }
        System.out.println("]");

        scanner.close();
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];

        // Step 1: 计算前缀积
        answer[0] = 1; // 前缀积起始为 1
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }

        // Step 2: 计算后缀积并直接更新结果
        int suffix = 1; // 后缀积起始为 1
        for (int i = n - 1; i >= 0; i--) {
            answer[i] = answer[i] * suffix; // 前缀积 * 后缀积
            suffix *= nums[i]; // 更新后缀积
        }

        return answer;
    }
}

代码解析

示例：`nums = [1, 2, 3, 4]`

前缀积（构建 answer 数组）：
- 初始化：answer[0] = 1
- 迭代计算：
  - answer[1] = answer[0] * nums[0] = 1 * 1 = 1
  - answer[2] = answer[1] * nums[1] = 1 * 2 = 2
  - answer[3] = answer[2] * nums[2] = 2 * 3 = 6
- 此时：answer = [1, 1, 2, 6]
后缀积（更新 answer 数组）：
- 初始化：suffix = 1
- 迭代计算：
  - answer[3] = answer[3] * suffix = 6 * 1 = 6
    - 更新 suffix = suffix * nums[3] = 1 * 4 = 4
  - answer[2] = answer[2] * suffix = 2 * 4 = 8
    - 更新 suffix = suffix * nums[2] = 4 * 3 = 12
  - answer[1] = answer[1] * suffix = 1 * 12 = 12
    - 更新 suffix = suffix * nums[1] = 12 * 2 = 24
  - answer[0] = answer[0] * suffix = 1 * 24 = 24
- 最终：answer = [24, 12, 8, 6]

时间复杂度

前缀积计算：遍历数组一次，时间复杂度为 O(n)。
后缀积计算：再遍历数组一次，时间复杂度为 O(n)。

总时间复杂度：O(n)。

空间复杂度

使用了常数级别的额外变量（例如 suffix）。
输出数组 answer 不算在额外空间中。

总空间复杂度：O(1)。

总结

为什么不能用除法？
- 除法需要预计算所有元素的总积，会出现除以零的问题，且不符合题目要求。
推荐方法：前缀积 + 后缀积
- 时间复杂度 O(n)，空间复杂度 O(1)。
- 高效、简洁，适合大规模数据。