LeetCode 补拙笔记

0. 前言

• 日期：2026.06.20
• 题目：238. 除自身以外数组的乘积
• 难度：中等
• 标签：数组、前缀积、后缀积

1. 题目理解

问题描述 给定整数数组 nums，返回结果数组 answer，answer[i] 等于数组中除 nums[i] 以外所有元素的乘积。 约束：禁止使用除法，时间复杂度要求 $O(n)$；进阶要求额外空间 $O(1)$（输出数组不计入额外空间）。

示例

输入：nums = [1,2,3,4] 输出：[24,12,8,6] 解释： answer[0] = 234 = 24 answer[1] = 134 = 12 answer[2] = 124 = 8 answer[3] = 123 = 6

2. 解题思路

核心观察

1. 公式推导：answer[i] = 左侧所有元素乘积 * 右侧所有元素乘积；
2. 基础解法：开前缀积数组 pre、后缀积数组 suf，空间 $O(n)$；
3. 进阶优化 $O(1)$ 额外空间：仅使用输出数组存前缀积，用单个变量遍历维护后缀积，取消独立pre、suf数组，消除边界if分支。

算法步骤

基础双数组法：

1. pre[i]：0~i所有元素乘积；suf[i]：i~末尾所有元素乘积；
2. 首元素仅乘后缀积，末尾元素仅乘前缀积，中间元素 = pre[i-1] * suf[i+1]。

进阶空间优化法：

1. 第一次从左向右遍历，输出数组存储每个位置左侧全部乘积；
2. 第二次从右向左遍历，用变量缓存右侧乘积，与数组内左侧乘积相乘得到最终结果。

3. 代码实现

package lc238;

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        int[] pre = new int[nums.length];
        int[] suf = new int[nums.length];
        int n = res.length;
        pre[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            pre[i] = nums[i] * pre[i - 1];
        }
        suf[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suf[i] = nums[i] * suf[i + 1];
        }
        res[0] = suf[1];
        res[n - 1] = pre[n - 2];
        for (int i = 1; i < n - 1; i++) {
            res[i] = suf[i + 1] * pre[i - 1];
        }

        return res;
    }
}

4. 代码优化说明

class Solution {
public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    int leftProd = 1;
    // 第一趟：填充左侧前缀积，无边界if判断
    for (int i = 0; i < n; i++) {
        ans[i] = leftProd;
        leftProd *= nums[i];
    }
    int rightProd = 1;
    // 第二趟：乘上右侧后缀积，统一处理全部下标
    for (int i = n - 1; i >= 0; i--) {
        ans[i] *= rightProd;
        rightProd *= nums[i];
    }
    return ans;
}
}

5. 复杂度分析

• 基础双数组原版 时间复杂度：$O(n)$，三次线性遍历；存在首、尾元素单独赋值的边界if分支 空间复杂度：$O(n)$，额外开辟pre、suf两个等长数组
• 进阶空间优化版 时间复杂度：$O(n)$，仅两次线性遍历，统一循环逻辑，消除首尾特殊if分支 空间复杂度：$O(1)$，仅两个常数变量维护左右乘积，输出数组不计额外空间

6. 总结

• 核心：利用前缀积 × 后缀积规避除法，满足题目限制；
• 优化亮点：舍弃独立前缀、后缀数组，复用输出数组存储左侧乘积，用单个变量维护右侧乘积，大幅降低空间开销；统一循环逻辑，删除首尾边界单独判断分支；
• 关键点：不能用除法，数组存在0会直接导致除法方案失效，前缀后缀积是唯一通用解法。