刷算法题的时候很多人一看“前缀和”三个字就有点怵觉得这是不是又是什么高深技巧。其实它内核就一句话把数组从头到尾的累计信息先算好存起来之后任何一个位置的查询都变成O(1)的查表。今天要拆的这两道题算是把这个思想玩得最透彻的入门经典——第27题“寻找数组的中心下标”和第28题“除自身以外数组的乘积”。两道题放在“优选算法-前缀和”这个专题里是绝配一个用前缀和求两侧和一个用前缀积加后缀积求两侧乘积。把这两题彻底吃透你基本就摸清了一整类“预处理 查表”的数组题套路。这篇文章就按我平时带人刷题的方式从为什么这么想开始一路讲到面试现场怎么答保证你读完能直接抄作业也能在面试官追问时站得住脚。1. 为什么偏偏是这两道题一个思路解决两类痛点先别急着看代码我们得先想明白一件事为什么讲前缀和往往拿这两道题开场因为它们表面上一个求下标、一个求乘积实际上背后是同一个困境——数组里的每个位置它的答案都同时依赖“我左边一堆元素”和“我右边一堆元素”的整体信息。如果每次遇到一个位置就去左边跑一遍、右边跑一遍时间就爆炸了。1.1 核心矛盾每个位置都要看“全局”第27题的中心下标要你在数组里找到一个位置让这个位置左侧所有数之和等于右侧所有数之和。注意这里的“左侧”和“右侧”都是连续的一段区间而且是动态变化的下标0要看右边所有数下标1要看左边1个数和右边n-2个数下标k要看左边k个数和右边n-k-1个数。如果每个下标都去数一遍那就是一层循环套一层循环O(n²)的复杂度。第28题更狠要求输出一个新数组其中每个位置的值等于“除自身以外所有元素的乘积”。比如数组[1, 2, 3, 4]下标0要输出2×3×424下标1要输出1×3×412以此类推。如果对每个位置都重新把除自己以外的数全乘一遍两次循环同样是O(n²)而且乘法可比加法费时多了数据一大基本就超时了。1.2 前缀和这类“预处理”到底在解决什么你可以把预处理想成这样一个场景你是一个班长要反复回答同学“我们班这次考试某某同学前面所有人的平均分是多少”这种问题。如果每次有人问你都从第一个人开始一个个往后加问一次算一次那也太累了。聪明的做法是考试出分后你先把每个同学“包括自己在内”的累计总分算好写在一张表上。之后再有人问某个同学前面的分数你查一下表做一次减法就出来了。前缀和干的就是这件事先花O(n)的时间把数组从头到尾的累计和算出来之后任何区间和查询都变成一次减法O(1)搞定。第27题用到的就是这个思路——我不用每个下标都重算左右两边的和而是先知道总和再从左往右维护一个“当前左侧和”右侧和直接拿总和一减就行。第28题则是把“和”换成了“积”从左往右预处理一份前缀积从右往左再预处理一份后缀积两个一乘答案就出来了。2. 先拿第27题练手中心下标是怎么一步步优化出来的这道题在LeetCode上的编号是724但很多训练营把它编成第27题。你去看讨论区有人一上来就写双重循环也能过但只要你把数据量放大到十万、百万立刻原形毕露。我们今天就完整演一遍这个思考过程。2.1 把题意翻译成人话边界条件最容易踩坑题目给一个整数数组nums要找一个下标满足“左边所有数的和”等于“右边所有数的和”。如果不存在就返回-1。这里有几个容易忽略的细节下标0的“左侧和”是0下标n-1的“右侧和”也是0。也就是说整个数组的总和为0时下标0或n-1可能就是答案你不能把左右两侧的“空区间”当成异常。如果有多个下标满足返回最左边那个。题目要求“最左边”所以从左往右扫找到第一个就返回。数组可能只有一个元素那么它自己就是中心下标因为左右两侧都是0。这些边界条件如果不在动手前想清楚代码很容易写出一堆if判断来修补最后变得又丑又容易错。2.2 暴力解法为什么能跑但不够好最朴素的写法是遍历每个下标i单独算左边和右边比一比。public int pivotIndex(int[] nums) { int n nums.length; for (int i 0; i n; i) { int leftSum 0, rightSum 0; for (int j 0; j i; j) { leftSum nums[j]; } for (int j i 1; j n; j) { rightSum nums[j]; } if (leftSum rightSum) { return i; } } return -1; }这个解法逻辑完全正确三个for循环最坏情况下每个i都要重新加一遍总操作次数差不多是n²/2。如果n是10万那就是50亿次加法在LeetCode上直接超时。这也是很多初学者卡住的地方不是不会写是写了以后不知道怎么往高效方向走。2.3 用前缀和切入从“每次重算”到“一次查表”优化的突破口特别简单我们每算一个位置的右侧和其实都在反复做同一件事——把一段区间的所有数加起来。如果先把总和total算出来那么对于下标i右侧和就是“总和 - 左侧和 - nums[i]”。这样一来我们只需要一个变量leftSum从左往右累加就能知道每个位置的左右两侧情况。判断条件就是leftSum total - leftSum - nums[i]成立说明当前下标就是中心点。这里有个特别容易写错的细节判断完之后再把nums[i]加进leftSum里。很多人顺手先把leftSum加上当前元素再判断结果永远找不到正确答案——因为leftSum已经被“污染”了。我的建议是判断语句放在更新之前如果相等直接返回如果不相等再执行leftSum nums[i]继续往后走。写成代码就是public int pivotIndex(int[] nums) { int total 0; for (int num : nums) { total num; } int leftSum 0; for (int i 0; i nums.length; i) { if (leftSum total - leftSum - nums[i]) { return i; } leftSum nums[i]; } return -1; }Python版也顺手放在这class Solution: def pivotIndex(self, nums: List[int]) - int: total sum(nums) left_sum 0 for i, num in enumerate(nums): if left_sum total - left_sum - num: return i left_sum num return -1整个过程只用了一次循环求和加一次循环判断时间复杂度O(n)空间复杂度O(1)——连额外数组都没用直接靠一个变量滚动。这就是前缀和思想的优雅之处你不需要真的开一个前缀和数组很多时候一个累计变量就够了。3. 第28题才是重头戏除自身以外数组的乘积这道题LeetCode编号是238面试出现频率极高因为它的限制条件非常“刁钻”不能用除法。如果题目没这个限制很多人第一反应肯定是先算总乘积然后每个位置除以自己。但这道题偏不让你这么做为什么因为用除法有三个致命问题一旦数组里有0除法就崩了即使没0整型除法还可能因为取整产生精度问题更别说面试官真正想考的压根就不是除法而是你是否理解“左右两侧信息各算一遍再合并”的思路。3.1 为什么“总乘积除以自己”是反面教材举个最简单的例子数组[2, 0, 3, 4]。总乘积是0算下标0的答案时0除了2还是0看着没问题。但到下标10除以0直接崩。有人可能说那先统计0的个数分类讨论也能做但代码会长出一堆分支而且面试官会觉得你在绕远路。如果你直接提出“先算总乘积再除以当前元素”大概率会收到一句灵魂反问“那如果数组里有0呢”所以这道题的正确姿势从一开始就要往“不依赖除法”的方向走。3.2 前缀积 后缀积把“除法”换成“乘法拼装”答案的思路非常直观对于位置i它最终的结果应该是“i左边所有数的乘积”乘以“i右边所有数的乘积”。我们没办法一笔算出整个结果那就拆成两半来算。先从左往右扫一遍用一个数组left其中left[i]表示nums[0]到nums[i-1]的累积乘积也就是“i左边所有数的乘积”。注意left[0]要初始化为1因为下标0左边没有元素空区间的乘积约定为1。再从右往左扫一遍用一个变量right表示当前下标右边的累积乘积。每扫到一个位置i就把ans[i]乘上right然后更新right right * nums[i]。这样一遍下来ans[i]正好等于左侧乘积乘以右侧乘积。Java代码public int[] productExceptSelf(int[] nums) { int n nums.length; int[] ans new int[n]; // 第一遍从左往右ans[i]先存左侧前缀积 ans[0] 1; for (int i 1; i n; i) { ans[i] ans[i - 1] * nums[i - 1]; } // 第二遍从右往左用right维护右侧后缀积 int right 1; for (int i n - 1; i 0; i--) { ans[i] * right; right * nums[i]; } return ans; }Python版class Solution: def productExceptSelf(self, nums: List[int]) - List[int]: n len(nums) ans [1] * n for i in range(1, n): ans[i] ans[i - 1] * nums[i - 1] right 1 for i in range(n - 1, -1, -1): ans[i] * right right * nums[i] return ans这里最关键的一点是第一遍结束后ans[i]里存的是“左边的乘积”第二遍再从右往左走用right变量把“右边的乘积”乘上去。整个过程没有新建额外的数组只用了一个常数变量right空间复杂度严格O(1)完全满足题目“输出数组不计入空间复杂度”的要求。3.3 为什么这个写法面对0也稳因为整个算法里没有除法操作全程都是乘法。哪怕数组里有0也不过是某一段前缀积或后缀积变成0最后ans里对应位置乘出来也是0。比如[0, 1, 2, 3]下标1的答案应该是0×2×30用我们的方法左侧乘积是0右侧乘积是60×60完全正确。所以“不用除法”这个限制表面上是刁难实际上是在保护你避开除零陷阱。如果你在面试时还能主动讲出“这样处理天然兼容0元素”这一点面试官好感度会直线上升。4. 把两道题的通用性看透一套左右夹击的模板前面两题的代码看着都短但它们的思维模式是一致的这个模式值得好好总结。很多刷题的人卡就卡在“每道题都像新题”其实是因为没把解法背后的骨架抽出来。4.1 抽出一个可复用的“左右信息”模型你会发现这两道题都在表达一个结构对于数组中的每个位置i它的答案由两部分信息构成——左侧区间[0, i-1]的某种聚合值以及右侧区间[i1, n-1]的某种聚合值。第27题是把“聚合值”定义为和要求左右两侧的和相等第28题把“聚合值”定义为积然后把左右两个积乘起来。更进一步这个“某种聚合值”不一定是和、积也可以是最大值、最小值、出现次数、哈希状态等等。比如经典的“接雨水”问题每个位置能存多少水取决于min(左侧最大高度, 右侧最大高度) - 当前高度。这就是同一套模板先从左往右预处理每个位置左侧的最大值再从右往左预处理右侧的最大值最后合并。如果你把第27、28题吃透了再看接雨水的题解会发现思路完全能对上。4.2 一道题怎么判断该不该用前缀和相关技巧我平时给人辅导时会教他们用三个特征来自检问题里频繁出现“区间求和/求积/求最值”而且这些区间是连续的一段每个位置的计算都依赖它左侧或右侧的一整块数据而不是只看相邻元素你脑子里已经浮现出“对每个下标先看左边再看右边两边合起来”这句话。如果三个特征中招了两个基本就可以考虑用预处理数组或者滚动变量来优化了。这比硬背模板有用得多因为判断优先级永远高于记忆优先级。5. 开发环境里的细节边界条件、溢出与特殊用例代码写得再漂亮边界条件守不住一到面试官的test case就露馅。我把这两道题里最容易翻车的地方单独拎出来讲一遍每个都是实际跑测试时踩过的坑。5.1 第27题总和的溢出风险这道题本身求的是和整数范围在LeetCode常规数据下不会溢出。但面试官可能会让你写一个更“抗造”的版本。我的建议是求total时用一个long来装最后判断时两边都转成long避免极端用例下int溢出。虽然这是细节但写出来会显得你很有经验public int pivotIndex(int[] nums) { long total 0; for (int num : nums) { total num; } long leftSum 0; for (int i 0; i nums.length; i) { if (leftSum total - leftSum - nums[i]) { return i; } leftSum nums[i]; } return -1; }然后回到上面的问题如果数组元素很大会怎样因为total可能超过Integer.MAX_VALUE但用long就没事了。不过注意负数这个题不会出现太多坑因为求和比较相等跟正负没太大关系。5.2 第28题前缀积的语言特性坑乘积比和更容易溢出但题目说了数据范围保证乘积在32位整数内所以int一般没问题。不过有三个点要注意数组长度为1时答案应该是[1]因为“除自身以外”没有元素空乘积约定为1。我们的代码天然覆盖这个情况。ans[0]先设为1代表左侧没有元素时的乘积这个“空积1”的约定必须想明白否则代码一改就容易乱。第二遍循环里先ans[i] * right再right * nums[i]顺序不能反。如果先把nums[i]乘进right再更新ans[i]那当前位置的结果就会多乘一个自身直接错。这个“先取用再更新”的顺序跟第27题里“先判断再累加”是同一个道理。很多bug不是思路错而是更新顺序写错了。5.3 一个很常见的错误数组遍历方向搞混第28题第一遍从左往右时ans[i]依赖的是ans[i - 1]所以必须从左往右遍历。第二遍从右往左时right依赖的是nums[i 1]到nums[n-1]的累积结果所以必须从右往左遍历。方向反了结果就全乱了。你在写代码时可以在注释里写清楚“从左往右算左侧积”“从右往左算右侧积”面试官一眼就能看懂你的思路也比代码本身更打动人。6. 面试现场怎么“表演”从写对到说得清很多读者技术上是没问题的代码一写就过但一到面试官追问就哑了。我建议你在面试时按下面这个顺序来表达这两道题的思路既清晰又能展示深度。6.1 先说暴力法再转折到优化面试官看到你直接写前缀和版本不一定能立刻判断你是“背了答案”还是“真懂了”。最好的做法是先简单提一句暴力法是O(n²)然后说“我们可以用前缀信息来避免重复计算”这样展示你的优化意识。哪怕是讲一道你已经很熟的题也不要一上来就甩最优解因为面试官想听到的是你的推理过程而不是答案本身。6.2 面试官高频追问和参考回答我整理了这两道题面试时最容易被问的三个问题参考答案也一并放在这你可以自己练一练问为什么第28题不用除法答除法遇到0会崩而且整型除法可能产生精度问题题目明确要求O(n)时间且不用除法用前缀积和后缀积是对题意的正解。问如果第28题允许用除法你会怎么做答先算总乘积nonZeroProduct再统计0的个数。如果0的个数大于1所有位置都是0如果0的个数等于1只有0那个位置是其他数的乘积其余都是0如果0的个数为0每个位置是总乘积除以自身。但我会说明这样虽然能做代码分支更多而前缀积/后缀积的做法不分情况统一处理更简洁。问第27题如果要求返回所有满足条件的位置怎么改答不直接return而是用一个list存下标扫完以后一次返回。核心判断逻辑完全不变。这几个追问一答完面试官基本就能确定你是真的理解而不是背板。6.3 现场讲思路时可以画的一个“口头图”不用真的动笔你可以在脑子里或纸上画一个三列表格左边是位置i的左侧区间中间是nums[i]右边是右侧区间。第27题问的是“左右的累计和相不相等”第28题问的是“左右的累计积相乘得到什么”。你把这个表格讲给面试官听胜过背一大堆术语。表达上多用“我先从左往右算一份左侧信息再从右往左算一份右侧信息”这样的话面试官会立刻知道你有结构化思维。7. 变式题与延伸把两道题的套路用到新场景说实话面试里直接考这两道的概率很高但更有可能考它们的“变式”。如果你只背代码不掌握背后的思想换个马甲你就认不出来了。这里给你两个最典型的延伸方向。7.1 从“前缀和”到“前缀最值”接雨水LeetCode第42题“接雨水”是面试高频。它问的是每个位置能存多少水计算公式是min(左侧最高柱子, 右侧最高柱子) - 当前高度。如果你一眼就能看出来这是“左侧信息 右侧信息 当前位置”三段式结构那这道题的解法就清晰了先从左往右维护一个leftMax数组记录每个位置左侧含自己的最大值再从右往左维护一个rightMax数组然后逐位计算。这跟第28题的“左侧前缀积 右侧后缀积”结构完全同构。唯一区别是聚合函数从“乘”换成了“max”。7.2 从“数组前缀”到“计数前缀”和为K的子数组LeetCode第560题“和为K的子数组”也是一道高频题它要求统计有多少个连续子数组的和等于K。如果不做优化就是O(n²)枚举所有子数组。但如果你熟悉前缀和你会发现子数组[j, i]的和等于prefix[i] - prefix[j-1]要找和为K就是找有多少个prefix[j-1]等于prefix[i] - K。于是可以边遍历边用哈希表记录前缀和出现的次数整个问题退化成一趟扫描。这个拓展能说明你对前缀和的理解已经不只停留在“算一遍区间和”而是掌握了“前缀和之间的差就是区间和”这个核心性质。8. 实战复盘从超时到一次通过的完整心路最后说说我实际跑这两道题的体会。第27题我刚学的时候是先写了暴力版本一提交小数据过大数据超时然后才开始想前缀和。后来第二次复习我尝试直接写优化版但第一遍还是差点写错——因为我把leftSum的更新顺序放错了导致中心下标总是偏一位。查了五分钟才发现原来是“先判断后累加”写成了“先累加后判断”。这个错误很典型大家写的时候一定留意。第28题我的感受是代码虽然短但“ans[i] * right”和“right * nums[i]”这两行很容易被初学者合并成一行或者顺序搞反。我第一次自己写时第二遍从右往左的循环里直接写成“right * nums[i]; ans[i] * right”结果所有结果都比正确答案多乘了一个自身。后来我把每一步的中间状态打印出来才意识到更新顺序必须遵守“先取用再更新”。这个经验之后我也用到其他题目上——凡是涉及滚动变量的题先想清楚“当前值是否还需要继续使用再决定更新时机”。建议你刷这两道题的时候也别急着写代码。先把nums [1, 7, 3, 6, 5, 6]和nums [1, 2, 3, 4]这两个例子用手推一遍算清楚每一步leftSum / total - leftSum - nums[i]或者ans[i]的中间值再打开编辑器写代码。手推一遍之后你再写代码就会顺畅得多因为脑子里的模型已经有了。我自己带人刷题时最常看到的现象是代码贴上去能过但把数组换一个、把条件稍微一改就不会了。所以要根治这个问题只能靠动手推演不能只靠看题解。这两道题作为前缀和的“门面题”非常合适用来建立这种推演习惯。你以后遇到任何“每个位置依赖左右两侧整体信息”的题目先条件反射地想想左侧信息怎么预处理、右侧信息怎么预处理、最后怎么合并这比记住任何具体题目的答案都要管用。