1. 题目核心与解题思路1.1 题目回顾与关键限制LeetCode Hot100刷到第13题刚好碰到一道经典的“中间难度”题——238. 除了自身以外数组的乘积。这道题在互联网大厂的后端/算法岗位面试中出场率极高几乎可以说是一道“手撕必考”题。题目本身不难读懂但它的限制条件很有讲究要求返回一个新的数组其中每个位置的值等于原数组中除该位置以外所有元素的乘积并且题目明确要求不能使用除法同时在O(1)额外空间复杂度内完成输出数组不计入额外空间。先看一下题目给的典型示例。输入数组是[1,2,3,4]输出应该是[24,12,8,6]。解释一下输出数组的第0位24 2*3*4第1位12 1*3*4第2位8 1*2*4第3位6 1*2*3。逻辑很清楚就是“把自己排除在乘法之外”。但这里有个很隐蔽的坑如果你第一反应是“先算出整个数组的乘积再除以每个位置自己”那么很快就会撞上边界条件——数组中一旦出现0除法方案直接报废因为0不能作被除数而0作为除数时结果会变得极其特殊多个0、单个0、没有0三种情况的处理方式完全不同。题目不让你用除法本质上就是想让你绕开这个坑回归到最朴素的“乘法累积”思路上。这道题适合正在准备算法面试的读者也适合刚把Hot100刷完前半段的同学。它不涉及高深的数据结构核心是考察你对“前缀/后缀”这类数组遍历技巧的掌握以及你在空间优化上的敏感度。说白了这道题不是让你背答案而是让你真的理解两次遍历是怎么把左右两边的乘积拼起来的。1.2 直观解法为什么走不通最容易想到的暴力解法就是双重循环对于每个位置 i重新遍历一遍数组把除了 i 以外的所有元素乘起来。时间复杂度是 O(n²)对于 LeetCode 上n 10^5的数据范围来说几乎是不可接受的。就算你优化一下用continue跳过自己累积乘法的次数依然是 n*(n-1)数据稍大就会超时。面试时你说出暴力思路面试官大概率会礼貌地点头然后让你“再优化一下”。既然不用除法那就要换个角度想。对于一个位置 i结果其实是“左边所有元素的乘积”乘以“右边所有元素的乘积”。这个拆解非常自然输出answer[i] prefixProduct[i-1] * suffixProduct[i1]。到这里一个清晰的 O(n) 方案就出来了——提前算好每个位置左侧的累积乘积和右侧的累积乘积再各取一个相乘。这是最常规、也最容易理解的正解很多教科书和题解都会先讲这个方法。但从面试角度看这还不算完因为题目要求 O(1) 额外空间很多初次接触的同学会卡在这一步不知道怎么能把两个辅助数组压缩掉。2. 常规解法左右乘积列表2.1 用两个辅助数组拆解问题先把常规做法展开来看。我们可以准备两个数组left和right长度都和原数组一样。left[i]表示原数组从第0位乘到第 i-1 位的结果right[i]表示从第 i1 位乘到末尾的结果。按照这个定义left[0]没有左边元素所以约定为1right[n-1]没有右边元素也约定为1。然后整个结果数组就是answer[i] left[i] * right[i]。以[1,2,3,4]为例。左数组从左往右推left[0]1left[1]left[0]*nums[0]1*11left[2]left[1]*nums[1]1*22left[3]left[2]*nums[2]2*36。右数组从右往左推right[3]1right[2]right[3]*nums[3]1*44right[1]right[2]*nums[2]4*312right[0]right[1]*nums[1]12*224。两者逐位相乘[1*24, 1*12, 2*4, 6*1]就是[24,12,8,6]。整个过程非常规整不会受到数组中是否有0的影响因为根本没有除法。这个解法的核心思想是把“一个位置的结果”拆成“左边累积结果”和“右边累积结果”的乘积也就是在讲一个“分治”故事当前问题的答案由左右两侧独立推导最后合并。这也是很多数组类题目的通用方法论比如“接雨水”那题也是用了类似的左右遍历思路。2.2 代码实现与逐行解读下面给出一个清晰度优先的 Python 代码面试时如果面试官没有明确要求空间优化你可以先把这个版本写出来保证逻辑正确。def productExceptSelf(nums): n len(nums) left [1] * n right [1] * n # 从左往右计算 left for i in range(1, n): left[i] left[i-1] * nums[i-1] # 从右往左计算 right for i in range(n-2, -1, -1): right[i] right[i1] * nums[i1] # 合并 answer [] for i in range(n): answer.append(left[i] * right[i]) return answer这段代码有三个循环时间复杂度 O(3n) 也是 O(n)空间复杂度 O(n)因为用到了两个辅助数组。这里我提一个很小的优化点合并那一步可以直接赋值给left数组这样能少开一个数组代码也会更整洁。不过即便如此两个辅助数组仍然占用了大量额外内存对于题目要求的“O(1)额外空间”来说还没达到。真正的挑战在于怎么把left数组的计算结果直接放到输出数组里再用一个变量滚动记录右侧累积乘积。3. 进阶优化O(1)额外空间的进阶写法3.1 复用输出数组与滚动变量面试官看完你刚才的代码通常会追问一句“能不用额外数组吗”这就是整道题的高潮部分。其实思路并不复杂因为输出数组answer本身是允许使用的我们完全可以把left数组的结果直接放在answer中先让answer[i]存下“左侧所有元素的乘积”。然后再考虑右侧从右往左遍历时用一个变量rightProduct滚动记录“当前位置右侧所有元素的乘积”每遍历到一个位置 i就把answer[i]乘上rightProduct同时把rightProduct更新为rightProduct * nums[i]让变量滚到前一个位置去。这种“滚动变量”的技巧非常常见本质上是把右侧数组的信息压缩进一次反向遍历中。很多读者第一次看到会觉得很精妙但多写几次就会发现它就是“前缀和”思想在空间上的延伸既然右侧的乘积只依赖当前位置后面的累积值那么不需要为每个位置都存一份只需要一个不断更新的变量就够了。3.2 完整代码与计算过程推演以 Python 为例最终优化版的代码非常简洁def productExceptSelf(nums): n len(nums) answer [1] * n # 第一次遍历answer[i] 记录左侧乘积 for i in range(1, n): answer[i] answer[i-1] * nums[i-1] # 第二次从右往左遍历用 rightProduct 记录右侧乘积 rightProduct 1 for i in range(n-1, -1, -1): answer[i] * rightProduct rightProduct * nums[i] return answer用[1,2,3,4]推演一遍。第一次遍历后answer [1,1,2,6]这分别代表第0位的左侧乘积为1第1位左侧乘积为1第2位左侧乘积为2第3位左侧乘积为6。接着初始化rightProduct 1从 i3 开始answer[3] * 1还是6然后rightProduct * nums[3]变成4i2 时answer[2] * 4变成8然后rightProduct * nums[2]变成12i1 时answer[1] * 12变成12然后rightProduct * nums[1]变成24i0 时answer[0] * 24变成24。最终answer [24,12,8,6]与题目完全一致。面试时我建议你先把这两个循环的意图说清楚再说边界第一个循环用answer数组本身存左侧乘积第二个循环用滚动变量做右侧乘积最后得到的结果就是两侧乘积的合并。这样讲面试官能立刻抓住你的思路也说明你不是背代码是真的理解了滚动变量。3.3 时间与空间复杂度对比下面用表格把两种实现对比一下版本时间复杂度空间复杂度额外数组数量是否满足题目要求暴力双重循环O(n²)O(1)0否时间超限左右辅助数组O(n)O(n)2或1部分满足空间不达标输出数组滚动变量O(n)O(1)0完全满足这里有一个容易误导的点有的同学会把“输出数组不算额外空间”记成“空间复杂度永远是 O(1)”这是不对的。题目明确说的“O(1)额外空间”是指除了返回结果所占用的空间之外你没有再使用额外的存储。如果过程中新建了两个长度和nums一样的数组那空间复杂度就是 O(n)即便你把结果赋给其中之一也只是少了一个依然是 O(n)。这个细节在面试中很敏感回答时宁可多说一句“我用输出数组本身来存放中间结果所以额外空间只有常量级”也不要含糊带过。4. 实战经验与面试复盘4.1 零元素与边界条件那点事很多人死记硬背代码但一遇到稍微变形的数据就懵了。最常见的问题就是数组里有0。回到题目两个0相乘是0一个0之外的乘积是0因此“自己除外”的结果可能全是0、可能只有一个非零值、也可能全部正常。用我们写的两次遍历法整个过程不涉及除法所以无论数组里有几个0都能正确处理。你可以拿[0,1,2,3]试一下第一个循环后答案是[1,0,0,0]第二个循环从右往左i3乘1得0rightProduct变成3i2乘3得0rightProduct变成6i1乘6得0rightProduct变成0i0乘0得0最终是[0,0,0,0]数学上完全正确——除第0位外的乘积是1*2*36但第0位本身的值为0这没问题。同理[1,2,0,4]会得到[0,0,8,0]也没问题。另一个边界是数组长度。题目通常会限定n 2因为长度为1时“除了自身以外”就没有任何元素了乘积怎么定义所以面试时你要主动询问或说明“假设数组至少包含两个元素”否则代码里会出现一些奇怪的数。还有空数组如果nums为空n0循环根本不会执行直接返回空列表就好但很多人的代码会因为answer[-1]这类访问而报错。我自己的习惯是在函数入口加一个if not nums: return []虽然题目可能不会出现空数组但多写一行总不会错。4.2 面试官会怎么追问完成 O(1) 空间版本后面试官可能会继续追问几个方向。第一个是“如果允许使用除法你会怎么做”这时你要先分析0的情况如果没有0先算总乘积再逐位除以nums[i]如果有一个0那么只有0那个位置的答案是总乘积跳过0计算的总乘积其余位置都是0如果至少两个0所有位置都是0。这个追问考察的是你思维的严谨性因为你如果没有提前想清楚0的分类讨论很容易写出有严重 bug 的除法实现。第二个追问是“能不能用多线程或并行计算来加速”这主要对应大数据场景。你可以说用前缀/后缀两次遍历天然是顺序依赖的但可以把数组分块每个分块内部先计算局部前缀/后缀再跨块合并最后用一个全局的累积变量来回填。这类题目在 LeetCode 上不多见但在面试里偶尔会聊到。第三个追问是“如果要求原地修改原始数组但返回值可以另开空间依然是 O(1) 吗”实际上就是让你在nums上先做一次左侧累积然后保存原始值再处理右侧比较绕。不过大多数场景下面试官只希望你解释清楚“为什么不能用除法”和“如何用两次遍历做到 O(1)空间”把这两点说透这题就基本过关了。4.3 同类题型的举一反三这道题的价值不只是本身它带出来的“前缀/后缀”思想在很多地方都能用。比如“接雨水”那题需要分别从左往右和从右往左找出每根柱子的左侧最高挡板、右侧最高挡板再叠加计算雨水量“统计小于当前元素的数量”这类题也会用前缀计数。我刷题时有一个经验看到“每个位置的结果仅与左右两侧有关”第一反应就是尝试“两次遍历滚动变量”。这个方法比什么动态规划都容易理解也容易向面试官讲清楚。LeetCode 238 看起来只是一道中等题但它的出题思路其实是面试官区分“背题型选手”和“理解型选手”的试金石。你如果能主动把“为什么不能除法”“0要怎么处理”“空间怎么压缩”三个问题讲透就算真正掌握了这道题。我个人刷完这题后在后续做“前缀和”相关题目时明显感觉思维顺畅了很多尤其是把“前缀积”和“前缀和”类比着看它们的套路完全一致一次遍历累计一个维度再看需要另一个维度就用反向遍历或滚动变量。所以如果你正卡在某道数组题没思路不妨想想 238 是怎么解的很多题就是它的变体。最后分享一个小技巧写这种题目先把思路口头说一遍再动手。你如果能在一分钟内说清楚“第一次遍历存左侧积第二次从右往左用变量存右侧积”代码基本一次就能写对。别一上来就抠语法把核心逻辑表达清楚面试官对你会非常有好感。这个习惯我从第 13 题开始养成后面每一道 Hot100 都按这个方法过效果好很多。