238.除自身以外数组的乘积 技术解析与实现

一、问题分析1.1 问题核心需求给定一个整数数组nums返回一个数组answer其中answer[i]等于nums中除nums[i]之外所有元素的乘积。核心约束的关键点的如下禁止使用除法避免出现除数为0的异常同时满足题目明确限制时间复杂度要求O(n)O(n)O(n)不能使用双重循环O(n2)O(n^2)O(n2)需设计线性时间的解题方案进阶要求可选额外空间复杂度O(1)O(1)O(1)输出数组answer不计入额外空间数据范围适配数组长度最大为10510^5105需保证算法高效避免超时元素取值范围为 [-30, 30]乘积在32位整数范围内无需考虑溢出问题。1.2 核心解题思路核心思路前缀乘积 后缀乘积。对于数组中每个元素nums[i]其除自身以外的乘积 左侧所有元素的乘积前缀乘积 × 右侧所有元素的乘积后缀乘积。分两步理解基础版额外空间O(n)O(n)O(n)计算前缀乘积数组prefixprefix[i]表示nums[0..i-1]的乘积即nums[i]左侧所有元素的乘积计算后缀乘积数组suffixsuffix[i]表示nums[i1..n-1]的乘积即nums[i]右侧所有元素的乘积最终结果answer[i] prefix[i] × suffix[i]。进阶优化额外空间O(1)O(1)O(1)不单独创建前缀、后缀数组直接利用输出数组answer存储前缀乘积再用一个临时变量存储后缀乘积反向遍历数组完成计算彻底节省额外空间。1.3 示例验证帮助理解以示例1nums [1,2,3,4]为例前缀乘积数组prefix[1, 1, 2, 6]prefix[0]1prefix[1]1×11prefix[2]1×22prefix[3]1×2×36后缀乘积数组suffix[24, 12, 4, 1]suffix[3]1suffix[2]4×14suffix[1]3×412suffix[0]2×3×424answer[i] prefix[i] × suffix[i] → [1×24, 1×12, 2×4, 6×1] [24,12,8,6]与示例输出一致。以示例2nums [-1,1,0,-3,3]为例因数组中存在0除0所在位置外其余位置的乘积均为00所在位置索引2的乘积 左侧乘积-1×1 × 右侧乘积-3×3 -1 × (-9) 9最终输出 [0,0,9,0,0]符合示例要求。二、完整代码实现基础版进阶版2.1 基础版额外空间 O(n)易理解基础版前缀后缀数组O(n)时间O(n)空间from typing import List class Solution: def productExceptSelf(self, nums: List[int]) - List[int]: n len(nums) # 1. 初始化前缀乘积数组prefix[i] 左侧所有元素的乘积 prefix [1] * n for i in range(1, n): prefix[i] prefix[i-1] * nums[i-1] # 2. 初始化后缀乘积数组suffix[i] 右侧所有元素的乘积 suffix [1] * n for i in range(n-2, -1, -1): suffix[i] suffix[i1] * nums[i1] # 3. 计算结果每个位置的乘积 前缀×后缀 answer [0] * n for i in range(n): answer[i] prefix[i] * suffix[i] return answer2.2 进阶版额外空间 O(1)满足题目进阶要求进阶版O(n)时间O(1)额外空间最优解from typing import List class Solution: def productExceptSelf(self, nums: List[int]) - List[int]: n len(nums) answer [1] * n # 输出数组先存储前缀乘积不计入额外空间 # 第一步计算前缀乘积存入answer for i in range(1, n): # answer[i] nums[0] * nums[1] * ... * nums[i-1] answer[i] answer[i-1] * nums[i-1] # 第二步计算后缀乘积用临时变量存储反向更新answer suffix_product 1 # 临时变量存储当前元素右侧所有元素的乘积 for i in range(n-1, -1, -1): # 此时answer[i]是前缀乘积乘以后缀乘积得到最终结果 answer[i] answer[i] * suffix_product # 更新后缀乘积加入当前元素下一次循环时当前元素成为右侧元素 suffix_product * nums[i] return answer三、代码核心解析3.1 基础版代码解析3.1.1 前缀乘积数组prefix初始化prefix [1] * n因为数组第一个元素索引0左侧没有元素其前缀乘积为1乘法单位元。循环从索引1开始prefix[i] prefix[i-1] * nums[i-1]含义是“当前元素的前缀乘积 前一个元素的前缀乘积 × 前一个元素的值”这样就能线性时间计算出所有元素的左侧乘积。3.1.2 后缀乘积数组suffix初始化suffix [1] * n数组最后一个元素索引n-1右侧没有元素其后缀乘积为1。循环从索引n-2开始反向遍历suffix[i] suffix[i1] * nums[i1]含义是“当前元素的后缀乘积 后一个元素的后缀乘积 × 后一个元素的值”线性时间计算出所有元素的右侧乘积。3.1.3 结果计算每个位置i的结果就是其左侧所有元素的乘积prefix[i]乘以右侧所有元素的乘积suffix[i]遍历一次即可得到最终数组。3.2 进阶版代码解析核心优化3.2.1 利用输出数组存储前缀乘积不再单独创建prefix数组直接用answer数组存储前缀乘积此时answer[i]的含义与基础版的prefix[i]完全一致节省了O(n)O(n)O(n)的空间。3.2.2 临时变量存储后缀乘积用suffix_product一个临时变量替代基础版的suffix数组。反向遍历数组时先将当前answer[i]前缀乘积与suffix_product后缀乘积相乘得到最终结果再更新suffix_product将当前元素nums[i]加入后缀乘积中为下一次循环左侧元素做准备。示例验证进阶版nums [1,2,3,4]前缀计算后answer [1, 1, 2, 6]反向遍历suffix_product初始为1i3answer[3] 6 × 1 6suffix_product 1 × 4 4i2answer[2] 2 × 4 8suffix_product 4 × 3 12i1answer[1] 1 × 12 12suffix_product 12 × 2 24i0answer[0] 1 × 24 24suffix_product 24 × 1 24最终 answer [24,12,8,6]与预期一致。3.3 关键细节说明初始化前缀/后缀乘积为1因为乘法的单位元是1乘以1不改变乘积结果确保边界元素第一个、最后一个的计算正确反向遍历的意义进阶版中反向遍历能让临时变量suffix_product逐步积累右侧元素的乘积无需额外数组存储无除法的核心通过“前缀后缀”的方式绕开除法既避免了除数为0的异常也满足了题目要求。四、时间/空间复杂度分析实现版本时间复杂度额外空间复杂度说明基础版O(n)O(n)O(n)O(n)O(n)O(n)用两个额外数组存储前缀、后缀乘积易理解进阶版O(n)O(n)O(n)O(1)O(1)O(1)利用输出数组和临时变量最优解时间复杂度两种版本均只遍历数组2-3次无嵌套循环因此时间复杂度为O(n)O(n)O(n)适配10510^5105长度的数组不会超时空间复杂度进阶版仅使用1个临时变量输出数组不计入额外空间满足题目进阶要求是实际面试中更推荐的写法兼容性两种版本均适配题目所有测试用例含负数、0且乘积在32位整数范围内无需额外处理溢出。五、关键注意事项避坑指南边界条件处理数组长度为2时题目提示n≥2n \geq 2n≥2如nums [a,b]结果应为[b,a]两种版本均能正确处理前缀/后缀乘积初始化为1遍历后计算正确0元素的处理无需单独判断0前缀后缀乘积的逻辑会自动处理——若当前元素是0其前缀×后缀就是其他所有元素的乘积若其他位置有0当前元素的乘积为0负数乘积的处理Python 支持负整数乘法无需额外处理符号前缀、后缀乘积会自动保留符号最终结果符号正确进阶版遍历顺序前缀计算需正向遍历后缀计算需反向遍历顺序不能颠倒否则会导致乘积计算错误临时变量更新时机进阶版中需先计算answer[i]再更新suffix_product否则会将当前元素nums[i]计入自身乘积导致结果错误。六、常见错误与优化建议6.1 常见错误错误1使用双重循环时间复杂度O(n2)O(n^2)O(n2)导致超时适用于小规模数组不适用于10510^5105长度错误2使用除法如总乘积 / nums[i]忽略了除数为0的异常且违反题目要求错误3进阶版中先更新suffix_product再计算answer[i]导致当前元素被计入自身乘积错误4前缀/后缀数组初始化错误未初始化为1导致边界元素计算错误。6.2 优化建议面试优先写进阶版O(1)O(1)O(1)额外空间的解法更能体现算法思维是面试官重点关注的解法先理解基础版再优化进阶版基础版的前缀后缀数组思路是核心进阶版只是空间上的优化理解基础版后更容易掌握进阶版多调试示例遇到错误时可结合示例1、示例2手动模拟遍历过程排查前缀、后缀乘积的计算逻辑。七、总结关键点回顾核心思想通过前缀乘积和后缀乘积绕开除法实现O(n)O(n)O(n)时间复杂度核心是“每个元素的结果 左侧乘积 × 右侧乘积”基础版用两个额外数组存储前缀、后缀乘积逻辑简单易理解适合入门进阶版利用输出数组和临时变量将额外空间优化至O(1)O(1)O(1)是最优解适合面试和实际开发避坑重点边界初始化、遍历顺序、临时变量更新时机以及0和负数的处理。本题是数组操作的经典题型核心考察“空间优化”和“线性时间算法设计”前缀后缀乘积的思路不仅适用于本题还可迁移到类似“求左侧/右侧元素乘积”的场景。掌握两种解法既能应对基础题目要求也能满足进阶的空间优化需求是面试中必须掌握的算法思路。