刷 LeetCode 的朋友应该都遇到过这道题238. 除自身以外数组的乘积。这题在许多公司笔试里出镜率极高凡是考“数组操作 时间复杂度优化”的组合很容易把它翻出来。我第一次看到题目要求“不能使用除法”的时候第一反应是“这么刁钻”后来想通前缀积思路后才发现它是数组类题目里非常典型的一次思维跳跃把一个结果拆成两个独立累乘过程再用同一块空间分两趟叠加。这道题适合所有正在刷 LeetCode 前 100 题的人尤其是刚接触“预处理数组”或者“空间复杂度优化”的读者。它不涉及高深的算法但非常考验对索引、边界和状态复用习惯的敏感度。这篇文章直接把我调试时踩过的坑、索引容易写错的位置、空间复杂度的理解一起讲清楚让你遇到这类“分成两半处理”的题目能直接迁移思路。1. 题目拆解为什么这道题能成为经典1.1 题目描述与样例原题要求很简洁给你一个整数数组nums返回一个数组answer其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。题目保证所有元素乘积不会超出 32 位整数范围示例是这样输入: nums [1,2,3,4] 输出: [24,12,8,6]原因很简单answer[0] 2*3*4 24answer[1] 1*3*4 12answer[2] 1*2*4 8answer[3] 1*2*3 6。每个位置都是“除了自己以外全部乘一遍”。这类题如果没限制第一直觉就是直接两层循环每个位置遍历其他所有元素相乘。可一旦数据规模到十万级别两层循环就是平方复杂度直接超时。所以“能不能一次遍历搞定”才是这题真正的考点。1.2 隐藏的约束条件禁用除法背后的原因题目还有一个隐藏约束不能使用除法。这其实是个非常有意思的设计。如果允许除法很多人会想到“先算所有元素的乘积再除以当前元素”。但这样做有两个致命问题如果数组里有 0除数变成 0直接报错。单独讨论 0 的个数又会让代码变得很啰嗦。很多实际场景里数据在内存中可能以流式方式读取或者乘积很大先用乘法再除法的做法容易放大中间值的误差或溢出风险。面试官把除法禁掉考察的是你愿不愿意放弃“最省事的数学公式”转而去设计一个不依赖特殊值的遍历方案。这种约束在真实工程里也很常见你手上拿到的数据可能不允许你预先计算全局聚合值尤其当全局聚合不稳定或占用过大时你会被迫用空间或重复遍历来换取稳定性。1.3 暴力法为什么不行有人会说“这题 O(n²) 也能过一部分测试数据”确实LeetCode 的示例规模不大但如果你真的提交一个双层循环版本在最后一个长测试用例上必挂。因为题目明确要求 O(n) 时间复杂度这是硬性指标。暴力解写起来没有难度def product_except_self_brute(nums): n len(nums) res [] for i in range(n): prod 1 for j in range(n): if i ! j: prod * nums[j] res.append(prod) return res它能跑通示例但复杂度摆在那里。更重要的是这种写法没有抓住题目背后的结构每个位置的答案其实可以被拆成“左侧连乘”和“右侧连乘”两部分而左右两侧的乘积都可以通过一趟扫描累计出来。一旦你看到这个结构代码量会少很多性能也会直接提升一个量级。2. 核心解法设计前缀积与后缀积的思维模型2.1 将乘积拆成两半左侧积与右侧积对于任意位置i我们想要的是answer[i] (nums[0] * nums[1] * ... * nums[i-1]) * (nums[i1] * ... * nums[n-1])左边这部分叫“前缀积”右边这部分叫“后缀积”。关键点是这两个积都和nums[i]无关所以你只要提前把每个位置的前缀积算出来再把每个位置的后缀积算出来最终结果一乘就行。用生活化的例子理解假设你在一排货架上站着老板让你把“自己手上货物以外所有货品的总价”算出来。你不需要把整排货架从头到尾扫一遍再排除自己你可以先从左往右逐位累乘得到“到每位为止左侧的总价”再从右往左扫描得到“每位右侧的总价”。两个总价一乘就是答案。这就是为什么这题被归类为“前缀和/前缀积”思想的经典代表。前缀和解决的是连续区间求和前缀积解决的是连续区间求积理解一个就能迁移到另一个。2.2 空间换时间的经典套路最容易想到的做法是准备两个辅助数组left和right。left[i] nums[0] * nums[1] * ... * nums[i-1] right[i] nums[i1] * nums[i2] * ... * nums[n-1]那么answer[i] left[i] * right[i]。这三个数组的构建都能在 O(n) 时间内完成先从左往右构建left再从右往左构建right最后一次性填answer。具体来说left[0]初始化为 1因为nums[0]左侧没有任何元素空积定义为 1。然后left[i] left[i-1] * nums[i-1]。右侧同理right[n-1]初始化为 1然后right[i] right[i1] * nums[i1]。这种做法的优点是逻辑非常直白适合笔试时作为第一版标准答案。缺点是使用了 O(n) 额外空间。如果题目不要求压缩空间交这个版本是稳妥的。我见过不少人在面试中先说出这个版本再一步步优化到 O(1) 额外空间这其实是最推荐的答题节奏先保证思路正确再展示优化能力。2.3 进阶版如何把空间压到 O(1)这里要理解题意里的一个关键细节输出数组不算额外空间。也就是说我们可以在answer数组自己身上反复利用先让它装左侧积再让它装“左侧积 × 右侧积”最终结果也正好存在这里。具体做法是第一趟从左到右让answer[i]存nums[i]左侧所有元素乘积。用变量right_product从右向左滚动维护右侧乘积。在扫描过程中answer[i] answer[i] * right_product然后更新right_product * nums[i]。通过这个做法辅助空间只剩下一个变量达到题目进阶要求的 O(1) 空间复杂度。代码实现几乎没有额外开销而且只遍历两遍时间复杂度依然是 O(n)。这是这道题最有价值的优化也是面试官最想看到你最终落地的代码。3. 代码实现与逐行解读3.1 Python 实现最简版Python 版本最容易写出简洁代码但也要小心索引越界。先看 O(n) 空间的两数组版本再看 O(1) 版本。O(n) 空间版本def product_except_self(nums): n len(nums) left [1] * n right [1] * n res [1] * n for i in range(1, n): left[i] left[i - 1] * nums[i - 1] for i in range(n - 2, -1, -1): right[i] right[i 1] * nums[i 1] for i in range(n): res[i] left[i] * right[i] return resO(1) 额外空间版本def product_except_self(nums): n len(nums) res [1] * n for i in range(1, n): res[i] res[i - 1] * nums[i - 1] right 1 for i in range(n - 1, -1, -1): res[i] * right right * nums[i] return res第二版里right是滚动右侧乘积。循环到i时right正好等于nums[i1]到nums[n-1]的乘积。然后更新right * nums[i]供下一个位置使用。这里顺序不能写反先乘再更新否则就把当前元素也乘进去了。3.2 C 实现与索引边界检查C 版本建议用vectorint注意nums.size()返回的是无符号类型如果直接做减法容易出问题。我习惯先把数组长度存成int n nums.size()避免后面n - 2出现无符号负数。class Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint res(n, 1); for (int i 1; i n; i) { res[i] res[i - 1] * nums[i - 1]; } int right 1; for (int i n - 1; i 0; --i) { res[i] * right; right * nums[i]; } return res; } };如果n为 0上面的循环不会执行返回空数组逻辑上是合理的。如果n为 1循环只会处理i 0此时right初始为 1所以res[0] 1这也符合“除自身以外所有元素乘积”的语义——一个元素时其他元素乘积为空积 1。我在实际写 C 时踩过一次坑忘记把vectorint res(n, 1)里的初值设为 1直接写vectorint res(n);。这样默认初始化为 0后面连乘全变 0。虽然不是编译错误但结果完全错误。所以初始化一定要显式给 1。3.3 Java 实现的注意点Java 版本和 C 相似但要注意数组自动初始化为 0 的问题更大。Java 的int[] res new int[n];默认所有元素为 0必须手动填充。class Solution { public int[] productExceptSelf(int[] nums) { int n nums.length; int[] res new int[n]; Arrays.fill(res, 1); for (int i 1; i n; i) { res[i] res[i - 1] * nums[i - 1]; } int right 1; for (int i n - 1; i 0; i--) { res[i] * right; right * nums[i]; } return res; } }Java 里Arrays.fill是常用的初始化方法也可以直接写for循环。从可读性上说Arrays.fill更直白。另一个容易忽略的点是如果数组元素中包含 0只要代码用的是“累乘但不除以任何元素”的方式就不需要特殊处理这是禁用除法带来的额外好处。我在面试时专门提到过这一点面试官通常会点头表示认可。4. 边界条件与性能细节4.1 数组为空的防御性处理题目一般不会给空数组但养成防御性思维没坏处。空数组时n 0返回空数组即可。如果你的代码里对n做了减一操作先判断一下或者直接用循环条件挡掉就不会越界。在工程代码里我会额外加一段注释说明空输入的行为而不是让调用方去猜。即使 LeetCode 不考这种习惯能避免线上问题。4.2 只有一个元素怎么办单元素数组很容易让人迷惑answer[0]应该是多少按照“除自身以外全部元素乘积”的定义没有其他元素所以乘积为空积 1。我们的算法天然支持这一点第一个循环不执行第二个循环中right初始为 1乘到res[0]上得到 1。如果你用“全局乘积除以自身”的除法版本单元素数组会得到x / x 1看起来一样但如果数组元素是 0就露馅了。所以前缀积做法在单元素场景下同样稳健。4.3 整数溢出与返回值类型LeetCode 原题说“保证数组内所有元素乘积不会超过 32 位整数范围”但在实际刷题过程中中间结果可能很大。比如nums [100000, 100000, 100000]res[0] 100000 * 100000就是10^10已经超出int范围。如果你在 C 或 Java 里使用int会面临溢出风险。LeetCode 官方题解使用int是因为约束条件保证但自己本地测试长数组时更稳妥的方式是使用long longC或longJava。我在 LeetCode 上见过不少讨论有人把res声明成long通过后又说题目要求返回int于是又强转回来。其实没必要纠结太多面试时问清楚数据范围根据范围选择类型即可。4.4 与“除自身”相关的变体题这题的变体非常多最常见的是“除自身以外数组的和”做法完全一样把乘法改成加法。还有“除自身以外数组的平均值”“带权乘积”等。甚至 leetcode 周赛里有些题目会把这种“左右累乘”思想嵌套到二维数组中比如“矩阵中每个位置等于四周元素乘积”核心思路仍然是一趟从左到右、一趟从右到左。我在做周赛 430 类似的题目时发现很多题都是 238 的壳子换了一层。看穿这一点后代码写起来就很快基本上只需要改累乘条件和维度。所以这题虽然难度不算高但迁移价值非常大。5. 常见问题与调试实录5.1 索引容易出错的三个位置第一是第一个循环的起始位置。很多人写成for i in range(0, n)导致res[0]被错误更新成res[-1] * nums[-1]产生数组最末一个元素的影响。正确写法是从 1 开始因为res[0]左侧没有元素默认是 1。第二是第二个循环的范围。从n - 2开始还是从n - 1开始如果已经用right变量记录右侧积循环必须从n - 1开始让最后一个位置先和初始值 1 相乘。如果从n - 2开始最后一个位置就没人管了。第三是更新顺序。res[i] * right之后一定要再执行right * nums[i]。如果把这两行交换right会先乘上当前元素再被用到下一个位置等于把自身元素也算进去了。这个问题非常隐蔽我第一次写的时候就因为顺序问题在索引n - 2的位置多乘了一个数输出结果整体偏移定位了很久。5.2 输出数组算不算额外空间的争议题目进阶要求里明确说了“输出数组不计入额外空间”但很多读者还会问那我在res里先存左侧积再存最终结果算不算额外空间答案是不算因为最终你总要返回一个同长度的数组。这个数组本身就是答案的载体不算额外辅助空间。但如果你另开一个left数组或right数组那就是额外的。这也是为什么“优化到 O(1)”的版本要复用res。面试时如果不确定直接和面试官确认“我可以在返回数组本身修改吗”一般都会允许。5.3 进阶思路的证明我们简单证明一下进阶做法为什么正确。第一趟结束后res[i]表示res[i] nums[0] * ... * nums[i-1]第二趟开始前right 1。当i n-1时乘上res[n-1]得到左侧积随后right nums[n-1]。当i n-2时right已经是nums[n-1]于是res[n-2]变成左侧积乘上nums[n-1]正好是除自身以外全部元素乘积。依此类推每个位置都满足要求。这个证明在面试时用两句话就能讲清楚“第一趟记录左边累积量第二趟用一个滚动变量从右边补上剩余部分。”重点不是背代码而是能把这个滚动过程讲明白。我在实际做这道题的时候最大的体会是空间复杂度的压榨往往只是代码顺序的调整而不是算法思路的根本改变。很多人一开始能写出 O(n) 空间的版本但一听到 O(1) 就卡住原因在于思维惯性觉得“需要另一个数组存右侧积”。其实一个变量就够用了关键在于要意识到右侧信息可以在遍历过程中实时滚动不需要随机访问历史值。最后再分享一个实战中很实用的调试技巧如果你写完后不确定索引对不对找一个长度 4 或 5 的小数组手动模拟两趟循环把每一轮res的值和right的值写下来对照一遍就能发现问题。这比反复提交 LeetCode 等判题快得多。熟练了以后这种“手动模拟两遍数组”的方法对我做其他前缀和、接雨水、买卖股票类题目帮助也特别大推荐你也养成这个习惯。