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

【每日算法】LeetCode238. 除自身以外数组的乘积

news 2026/5/12 10:00:16

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

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

1. 题目描述

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

不能使用除法。
时间复杂度为 O(n)。
空间复杂度为 O(1)（不计算输出数组的空间）。

进阶：你可以在 O(1) 额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

示例：

输入: nums = [1,2,3,4]
输出: [24,12,8,6]
解释: answer[0] = 234=24, answer[1] = 134=12, 以此类推。

2. 问题分析

这个问题要求计算数组中每个元素除自身外所有其他元素的乘积。直接思路包括：

使用除法：先计算总乘积，然后除以每个元素。但题目禁止使用除法，且如果数组中有零元素，会导致除零错误或结果不准确。
暴力计算：对于每个元素，遍历数组计算乘积，但时间复杂度为 O(n²)，不满足要求。
因此，需要一种高效算法，在 O(n) 时间内完成，且空间开销最小。核心是避免重复计算，利用前缀和后缀乘积的思想。

3. 解题思路

3.1 思路一：暴力法（不推荐）

对于每个索引 i，遍历数组计算除 nums[i] 外所有元素的乘积。时间复杂度 O(n²)，空间 O(1)（输出数组除外）。不满足题目要求，仅用于理解问题。

3.2 思路二：左右乘积列表

维护两个数组：

left[i]表示 nums[0] 到 nums[i-1] 的乘积（即 i 左侧所有元素的乘积）。
right[i]表示 nums[i+1] 到 nums[n-1] 的乘积（即 i 右侧所有元素的乘积）。
然后，answer[i] = left[i] * right[i]。这通过两次遍历实现：一次从左到右计算左乘积，一次从右到左计算右乘积。时间复杂度 O(n)，空间 O(n)（用于存储左右乘积列表）。

3.3 思路三：空间优化版左右乘积（最优解）

在思路二的基础上进行空间优化：

使用输出数组answer先存储左乘积（即answer[i]初始为左侧所有元素的乘积）。
然后从右向左遍历，用一个变量rightProduct累积右侧元素的乘积，并乘以answer[i]得到最终结果。
这样，时间复杂度 O(n)，空间复杂度 O(1)（忽略输出数组），满足进阶要求。这是最优解，因为它平衡了时间和空间效率。

4. 各思路代码实现

4.1 思路一代码实现（暴力法）

functionproductExceptSelf(nums){constn=nums.length;constanswer=newArray(n).fill(1);for(leti=0;i<n;i++){for(letj=0;j<n;j++){if(i!==j){answer[i]*=nums[j];}}}returnanswer;}

4.2 思路二代码实现（左右乘积列表）

functionproductExceptSelf(nums){constn=nums.length;constleft=newArray(n).fill(1);constright=newArray(n).fill(1);constanswer=newArray(n);// 计算左乘积for(leti=1;i<n;i++){left[i]=left[i-1]*nums[i-1];}// 计算右乘积for(leti=n-2;i>=0;i--){right[i]=right[i+1]*nums[i+1];}// 计算答案for(leti=0;i<n;i++){answer[i]=left[i]*right[i];}returnanswer;}

4.3 思路三代码实现（空间优化版）

functionproductExceptSelf(nums){constn=nums.length;constanswer=newArray(n).fill(1);// 第一步：计算左乘积并存入 answerletleftProduct=1;for(leti=0;i<n;i++){answer[i]=leftProduct;leftProduct*=nums[i];}// 第二步：从右向左遍历，乘上右乘积letrightProduct=1;for(leti=n-1;i>=0;i--){answer[i]*=rightProduct;rightProduct*=nums[i];}returnanswer;}

5. 各实现思路的复杂度、优缺点对比表格

思路	时间复杂度	空间复杂度（除输出外）	优点	缺点	是否满足题目要求
暴力法	O(n²)	O(1)	简单直观，易于实现	效率极低，不适用于大数据集	否
左右乘积列表	O(n)	O(n)	高效，逻辑清晰，易于理解和调试	使用额外 O(n) 空间，未优化空间	是（时间满足，空间未优化）
空间优化版	O(n)	O(1)	时间和空间最优，满足进阶要求	代码稍复杂，需注意遍历顺序	是（最优解）