除自身以外数组的乘积：前缀积与后缀积的两趟扫描解法-北京尧图网络

1. 题目拆解与解题突破口1.1 一道看似简单却容易掉进坑里的数组题LeetCode 238 在算法练习平台上出现频率非常高题目本身一句话就能说清给你一个整数数组 nums返回一个新数组 answer其中 answer[i] 等于原数组中除 nums[i] 以外所有元素的乘积。示例 [1,2,3,4] 对应结果就是 [24,12,8,6]。我第一次看到这道题时觉得很简单真上手写才发现坑不少不能直接用除法还要考虑 O(n) 时间复杂度和 O(1) 额外空间输出数组本身不算额外空间这些限制叠加在一起时暴力解法根本过不了。适合什么人看不管是刚开始刷算法题的学生还是准备面试的工程师这道题都属于必练基础题。它考察的内容并不高深核心是对“数组前缀信息”的敏感度。C 和 Java 两种写法我都实际练过核心逻辑完全一样只是语言细节上有些差别下面我会把两种语言都展开讲清楚。简单说这道题的价值在于用最低的语法难度逼着你理解“把一侧的乘积存下来另一侧滚动计算”的经典套路。这个套路后面在很多问题上都能复用尤其是跟“前缀和”“差分数组”沾边的一类题目。1.2 暴力解和除法解为什么都走不通先说暴力解。对于每个位置 i遍历整个数组把所有不等于 i 位置的数乘起来示例 [1,2,3,4] 每个位置都要额外做 n-1 次乘法整体复杂度 O(n²)。数组长度只要到 10^5 级别这种解法就直接超时完全没有讨论价值。然后是除法解。你可能会想先算出整个数组的乘积 total然后 answer[i] total / nums[i]一次遍历搞定多漂亮。这个思路在完全没有 0 的数组上确实成立但一遇到 0 就崩。nums[i] 0 时除数为 0直接运行时报错数组里有多个 0 时还得分类讨论“0 的个数是 0 个、1 个还是多个”每个分支公式都不一样代码越改越长。更重要的是题目明确写了“请不要使用除法”。所以这条路线不仅是被语法禁止逻辑上也很麻烦。真正正确的方向不是想办法绕开 0 的除法而是从根上换一种组合方式把 answer[i] 拆成“i 左边所有数的乘积 × i 右边所有数的乘积”。全程只有乘法完全没有 0 和除数的问题。这个拆法来自一个朴素观察乘法满足交换律和结合律一个数组的元素分成左右两部分相乘跟“一路连乘到当前位”是等价的。既然不能直接把 nums[i] 从总乘积里除掉那就干脆不让 nums[i] 进入任何一次计算。左右两侧分别算好再乘在一起这就是整道题的钥匙。2. 核心算法前缀积与后缀积的两趟扫描2.1 前缀积怎么理解“前缀积”这个词不复杂。用一个数组 prefixprefix[i] 表示从 nums[0] 一直乘到 nums[i-1] 的结果也就是当前位置左边所有数的乘积。关键点是 prefix[0] 是多少。0 号位置左边没有任何元素数学上把它设成 1。乘以 1 不改变结果这样后面递推时公式才能统一prefix[i] prefix[i-1] * nums[i-1]。这里我建议你重点看下标错位。很多人第一次写会写成 prefix[i] prefix[i-1] * nums[i]结果把自己也算进去了。为什么要用 nums[i-1]因为 prefix[i] 明确表示“到 nums[i-1] 为止的累积”它不包含 nums[i]。比如数组 [1,2,3,4]prefix[0] 1prefix[1] 1 * 1 1prefix[2] 1 * 2 2prefix[3] 2 * 3 6你会发现 prefix[3] 123 6正好是数组前三个元素的积不含第 4 个元素。这个错位是整道题最容易错的地方记住“算当前位置答案时前缀只包含它左边的元素”这个原则。2.2 后缀积怎么构建以及空间怎么省掉后缀积同理。用 suffix 数组suffix[i] 表示从 nums[i1] 一直乘到数组末尾的乘积也就是当前位置右边所有数的乘积。最后一个位置 n-1 右边没有元素所以 suffix[n-1] 1。递推公式是 suffix[i] suffix[i1] * nums[i1]。两个数组都有了之后answer[i] prefix[i] * suffix[i]答案一次成型。这种写法逻辑最清晰也最不容易出错是我个人最推荐的首选思路。但题目经常附加“额外空间复杂度 O(1)”的要求。注意这里的定义输出数组 answer 不算额外空间。所以可以复用 answer 数组来当 suffix 数组用。具体做法是第一遍从右往左填 answer让 answer[i] 存后缀积第二遍从左往右遍历维护一个变量 left 作前缀积每到一个位置就把 answer[i] 再乘上 left然后更新 left。除了输出数组本身只多了一个变量额外空间严格 O(1)。为什么能复用因为后缀积只需要被乘一次等它用于生成最终答案之后原位置的信息就没有保留价值可以放心覆盖。很多空间优化题的思路都和这类似用“遍历顺序”和“中间变量”替代额外数组。2.3 手算示例一眼看清两趟扫描做了什么还是用 [1,2,3,4] 演示一遍。第一趟从右往左构建后缀积answer[3] 1因为右边没有元素answer[2] answer[3] * nums[3] 1 * 4 4answer[1] answer[2] * nums[2] 4 * 3 12answer[0] answer[1] * nums[1] 12 * 2 24此时 answer [24, 12, 4, 1]每个位置存的是“右侧所有数的积”。比如 answer[1] 3*4 12和公式完全吻合。第二趟从左往右用 left 记录前缀积left 1i0answer[0] * 1 仍是 24更新 left * nums[0]left 变成 1i1answer[1] * 1 变成 12更新 left * nums[1]left 变成 2i2answer[2] * 2 变成 8更新 left * nums[2]left 变成 6i3answer[3] * 6 变成 6更新 left * nums[3]left 变成 24最终 answer [24, 12, 8, 6]完全正确。注意“先乘再更新”的顺序不能反。如果先更新 left 再乘i2 时就会乘上已经包含 nums[2] 的前缀积答案就错了。这个顺序问题在面试现场很容易因为紧张写反写完用一个小例子在纸上跑一遍是最快的检查方法。3. C 实现从标准写法到空间优化3.1 两个辅助数组的经典写法C 代码用 vector 最方便两个辅助数组版本如下class Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint prefix(n, 1), suffix(n, 1), ans(n, 1); for (int i 1; i n; i) { prefix[i] prefix[i-1] * nums[i-1]; } for (int i n-2; i 0; i--) { suffix[i] suffix[i1] * nums[i1]; } for (int i 0; i n; i) { ans[i] prefix[i] * suffix[i]; } return ans; } };这段代码里 prefix 和 suffix 的初始值都设成 1n 至少为 2三个循环都能正常跑。三个循环相互独立思路直白几乎没有任何隐蔽的坑。笔试时求稳这个版本是最合适的选择。这里有个面试小技巧先写这个版本然后向面试官说明“还能把空间优化到 O(1)”最后再手写优化版。这样既能展示思路清晰又能展示优化意识比上来直接写 O(1) 版本要稳妥。因为 O(1) 版本一旦写错调试成本比较高两个辅助数组版本出错概率低很多。3.2 O(1) 空间的滚动写法优化版核心思想用 answer 数组先存后缀积再用 left 变量滚动累乘前缀积class Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint ans(n, 1); // 第一趟从右往左记录右侧累积积 int right 1; for (int i n-1; i 0; i--) { ans[i] right; right * nums[i]; } // 第二趟从左往右乘上左侧累积积 int left 1; for (int i 0; i n; i) { ans[i] * left; left * nums[i]; } return ans; } };这个版本注意第一趟不需要单独给 ans[n-1] 赋值 1因为循环从 n-1 开始第一步就执行 ans[n-1] right而 right 初始是 1。第二趟中变量名我故意用 right 和 left实际含义分别是“当前遍历方向上的累积乘积”命名按自己容易理解的方式来就好。很多题解会用 prefix 和 suffix 命名但在 O(1) 版本里这两个变量其实分别是“左侧累积值”和“右侧累积值”。我习惯按语义命名为 leftProduct 和 rightProduct能有效避免混淆。3.3 C 实现时的细节问题第一个细节是乘积溢出。LeetCode 这道题保证 answer 在 32 位整数范围内所以 int 是安全的。但如果本地测试时把数据加大或者数组长度拉满再用大数去乘中间变量可能溢出。稳妥做法是改成 long long 做累积最后再转回 int。第二个细节是 vector 的初始化。vector ans(n, 1) 比默认初始化为 0 更安全。因为如果某些分支没赋值至少是 1 而不是 0排查时少一个干扰因素。第三个细节是循环变量类型。n - 2 这种表达式在 n 很小的时候没问题但如果写成 for (int i n - 1; i 0; i--) 而 n 是无符号的 size_t就比较危险。size_t 是无符号类型i-- 到 0 以后继续减会变成很大的正数可能死循环甚至越界。统一用 int 就能避免这个坑。4. Java 实现从标准写法到空间优化4.1 Java 最简写法Java 和 C 的思路完全一致代码结构上更好读一些因为数组语法比 vector 更轻量class Solution { public int[] productExceptSelf(int[] nums) { int n nums.length; int[] ans new int[n]; // 从右往左先存右侧乘积 ans[n - 1] 1; for (int i n - 2; i 0; i--) { ans[i] ans[i 1] * nums[i 1]; } // 从左往右乘上左侧乘积 int left 1; for (int i 0; i n; i) { ans[i] * left; left * nums[i]; } return ans; } };这里我单独把 ans[n-1] 1 提出来是为了让循环从 n-2 开始避免访问 ans[n] 越界。如果你更喜欢从 n-1 起步的写法也可以配合临时变量使用但提出来后代码更直观新手不容易错。第二趟循环里ans[i] * left 这行在 left 更新之前执行。很多人问为什么不能先更新 left 再乘 ans[i]因为 left 应该表示“nums[0] 到 nums[i-1] 的乘积”一旦先乘 nums[i]left 就包含了当前位置的元素乘到 ans[i] 上相当于把自身也算进去了答案必然错误。4.2 两个辅助数组的对照写法初学阶段或者想跟面试官把思路讲得更透彻时两个辅助数组版本在 Java 里长这样class Solution { public int[] productExceptSelf(int[] nums) { int n nums.length; int[] prefix new int[n]; int[] suffix new int[n]; prefix[0] 1; for (int i 1; i n; i) { prefix[i] prefix[i - 1] * nums[i - 1]; } suffix[n - 1] 1; for (int i n - 2; i 0; i--) { suffix[i] suffix[i 1] * nums[i 1]; } int[] ans new int[n]; for (int i 0; i n; i) { ans[i] prefix[i] * suffix[i]; } return ans; } }两个版本的逻辑一致差异只在空间。笔试时如果题目只要求 O(n) 时间、没限制空间写两个辅助数组最稳面试时如果明确提到“尽量避免额外空间”就用 4.1 的滚动版本。两个版本都要熟因为面试官很可能在你写完一个版本后追问“还能不能更省空间”。4.3 Java 与 C 在实现上的差异对照两种语言的实现我感受比较深的有三点。第一数组默认值不同。C 的 vector 如果不传初始值默认初始化为 0Java 的 int[] 默认也是 0。看起来一致但边界位置必须显式设置成 1不要依赖任何默认行为。第二循环边界写法。Java 的数组长度是 int 类型不存在 C 里 size_t 和 int 混用的问题但同样要注意 n-2 不能写成 n-1否则第一次循环就越界。我过去习惯从 n-1 开始结果每次都要特判后来干脆改成先赋值再倒着遍历彻底根治了这个问题。第三命名习惯。Java 社区更常见用 result 做返回数组C 社区更常见用 ans。这种差异不影响正确性但保持上下文一致能让读者更容易跟下来。我习惯统一用 ans因为它在题解和博文里出现频率高读者不陌生。5. 常见错误与排查心得5.1 四个高频 Bug第一个高频 Bug 是答案数组全变成 0。原因通常是后缀积那趟从数组初始值开始往前填而 Java/C 数组默认值是 0导致后续所有位置都乘上 0。解决办法是把最后一个元素的边界值先赋成 1或者用临时变量在循环内先赋值再乘。第二个高频 Bug 是某个答案里包含了自身。原因几乎都是更新 left/right 和乘到 ans 的顺序写反。记住口诀先算当前答案再更新累积变量。只要顺序对“除自身以外”这个条件就天然满足。第三个高频 Bug 是越界异常。Java 会直接抛数组越界异常C 则是未定义行为表现可能是崩溃也可能随机出错。最常见的越界是循环里访问 nums[i1] 时 i 已经到 n-1或者访问 prefix[i-1] 时 i 从 0 开始。写完后用长度为 2 的小数组快速走一遍基本就能查出来。第四个高频 Bug 是以为 n1 需要特判。这道题约束 n 2正常情况下不需要处理长度为 1 的数组。如果你在本地测了 n1代码能不能输出 [1]不一定要看循环写法。为了心里有底可以在草稿纸上推一下但完全没必要在代码里加分支。5.2 问题速查表与调试建议症状可能原因修复方法最终答案数组全为 0后缀积初始化位置被设为 0将 ans[n-1] 设置为 1再倒序填充某一个答案多了自身因子left/right 先更新再乘调整顺序先乘答案再更新累积值数组越界异常后缀循环从 n-1 开始访问 i1改为从 n-2 开始或先赋值边界返回了空数组忘记 return ans检查函数末尾是否有返回语句大数组乘法结果异常int 溢出或 size_t 循环陷阱改用 long long或统一用 int 控制边界调试建议我最常用的是“小样例打印法”。拿 [1,2,3,4] 这种长度为 4 的数组配合纸笔把两个循环的中间值都写出来再跟代码走一遍对比。这个方法对前后缀类问题尤其好用因为每个中间值都有明确语义对得上就说明思路正确。5.3 边界测试用例推荐除了标准示例 [1,2,3,4]我建议重点测四类数据全是正数的小数组比如 [2,3]答案应该是 [3,2]用来验证最小区间。包含零的数组比如 [0,1,2]答案应该是 [2,0,0]。前缀积做法不需要任何特殊判断也能正确处理这是它比除法强的关键体现。包含负数的数组比如 [-1,2,-3]答案应该是 [-6,3,-2]。自己算一下第一个位置等于 2*(-3)-6第二个位置等于 (-1)*(-3)3第三个位置等于 (-1)*2-2。长度为 2 的边界数据比如 [5,6]答案 [6,5]。这些用例覆盖了符号、零、最小规模三类边界能跑通就说明代码基本稳了。尤其是含零用例如果你写的是除法版本这里就开始头疼用前后缀版本则一路畅通。6. 扩展思考变体、追问与实际应用6.1 如果允许除法解法会变成什么样实际面试里很多面试官会在你写完前后缀解法后追问一句“如果这道题允许用除法你会怎么写”这不是让你推翻现在的答案而是考察你对边界情况的敏感度以及能不能在约束变化时迅速调整策略。允许除法时标准做法是按数组中 0 的个数分类讨论0 的个数为 0先求总乘积 total然后 answer[i] total / nums[i]0 的个数为 1只有那个为 0 的位置答案等于除它以外所有数的乘积其它位置答案全为 00 的个数大于等于 2所有位置的答案都是 0。你会发现即使允许除法代码也要写三种分支一点不比前缀积简单还要担心精度问题。所以面试官问这个问题的真实意图往往是让你体会“前后缀积为什么是更本质的解法”。能把上面三种情况讲清楚比单纯回答“可以除”要加分很多。6.2 前后缀思想的工程应用前后缀积不只在算法题里有用工程上也有实际场景。第一个场景是“排除某个维度的组合计算”。比如某些推荐场景里要为每个用户计算不包含当前物品时其它物品的综合分数。如果每个位置独立重算复杂度是 O(n²)利用前缀后缀一次预处理加一次遍历就能批量算完全部位置。第二个场景是“滑动窗口统计”。滑动窗口的均值、方差以及很多需要排除当前项的统计量底层思路都和这道题一脉相承把总量拆成左边和右边再用滚动变量维护一侧的累积状态。连续子数组相关问题也经常会用到类似的前缀信息优化。6.3 这道题真正想考察的思维方式刷完这道题我最大的收获不是背下代码而是建立了一个条件反射看到“数组里除当前元素外的某种整体属性”第一反应就是能不能分成“左侧”和“右侧”两部分单独算。这个条件反射的来源是乘法天然可拆分的性质。left 和 right 分别用一个 O(n) 遍历维护最后用一次遍历合并整体复杂度 O(n)。空间上复用输出数组又能把辅助数组压掉只留 O(1)。这道题也提醒我做算法题时不要急着绕开限制而是看清限制背后的动机。题目禁用除法不是故意为难人而是因为除法在存在 0 时根本不稳健。前后缀积方案不仅满足时间和空间限制还天然免疫 0这才是更符合工程直觉的方案。从我反复刷这道题的经验来看最有效的记忆方式不是死记代码而是建立“右侧存数组、左侧滚动乘”的画面感。你可以在脑子里闪现两个循环第一趟从右往左在 answer 里铺后缀积第二趟带着 left 变量从左往右边乘边更新。每次写题前先拿 [1,2,3,4] 走一遍流程再落到代码基本一次就能写对。如果你刚开始接触这类题目我建议先用两个辅助数组版本跑通再对照优化版逐行理解为什么可以复用。等到能不看任何参考写出两个版本而且能讲清楚边界赋值 1 的原因这道题才算真正掌握。以后遇到前缀和、前缀积、差分这一类问题思路都会顺畅很多。

除自身以外数组的乘积：前缀积与后缀积的两趟扫描解法

相关推荐

老版本摄像头驱动在Win10下的安装与DirectShow采集避坑指南

自建电气元件选型工具：从参数库到评分筛选的完整指南

Kubernetes 1.18.8 部署实战：兼容老系统与边缘场景的稳态集群搭建

更多资讯

STM32+华为云IoT+Qt：从零搭建智能家居全链路控制系统

Spring Boot动态定时任务：基于数据库配置cron，无需重启实时生效

Spring Boot同名类Bean名冲突全解析：从原理到五套解决方案

Spring Boot同名类Bean名冲突：原因分析与五套解决方案

单片机C库运行时：从libspace到中断安全的多任务可重入实践

微信小程序K线图开发实战：HQChart集成与通达信公式解析

今日更新

防关联浏览器哪个好？三款产品实测差异解析

2026钢铁行业AI转型系统选型对比：多基地排产、大宗原燃料采购与质量追溯，六家厂商能力差异在哪里

影刀RPA深度实战：大模型Fine-tuning定制RPA专用Prompt与指令生成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？