空间优化)
刷到 LeetCode 热题 100 里的“除自身以外数组的乘积”时我第一反应是这题有什么难的算出全体乘积再逐个除掉不就行了仔细一看题目明确要求不要使用除法还希望额外空间做到 O(1)——这一下就把大多数人最顺手的暴力思维堵死了。本文用 Java 把这个题从暴力解法一路拆到空间优化的最优实现把每一步的思路、代码和真正坑过我的细节都写清楚。无论你是刚准备面试的应届生还是想补算法短板的在职开发这题都是一个非常好的“渐进优化”训练样本。1. 这道题到底在考什么为什么“除法”被明令禁止1.1 题目定义与两个关键示例先把题目说清楚。给定一个整数数组nums请返回一个同样长度的数组answer其中answer[i]是原数组中除nums[i]之外所有元素的乘积。题目给出的限制里有两条最扎眼不使用除法且在使用 O(1) 额外空间的条件下完成输出数组不计入额外空间。示例输入: [1,2,3,4] 输出: [24,12,8,6] 输入: [-1,1,0,-3,3] 输出: [0,0,9,0,0]第一个例子很常规第二个例子专门放了一个 0。别小看这个 0它直接影响你能否用除法偷懒。1.2 “总乘积除以自身”方案的致命伤很多人的第一直觉是先算total nums[0] * ... * nums[n-1]然后answer[i] total / nums[i]。这段逻辑在没有 0 的数组上完全正确还能做到 O(n) 时间、O(1) 空间看起来比任何优化都要强。但只要数组里出现一个 0这条路就断了total是 0遇到nums[i] 0时直接除零异常就算用特判躲过去你也必须反复统计 0 的个数才能确定哪些答案是 0、哪个答案是“除 0 外所有元素的乘积”。这道题把除法禁掉本质上是逼你去想比“总体乘积倒推”更本质的做法。1.3 真正要掌握的核心洞察左右拆分再看answer[i]的构成。对于[a, b, c, d]answer[2] a × b × d。把数组以当前位置为界劈成两半a × b是左边部分的乘积d是右边部分的乘积——answer[i]永远等于“左侧所有元素的乘积 × 右侧所有元素的乘积”。题目立刻从“求全局乘积再剔除自己”变成了“分别预计算每个位置左侧和右侧的累积乘积再相乘”。这就是解这道题的地基也是它想考察的思维模型当每个输出都依赖“除自身之外的整体信息”时不要老想着从整体中剔除自己而是把整体拆成两个可预计算的半边最后拼起来。2. 暴力解法不是废柴先把能跑对的版本写出来2.1 双重循环的完整实现哪怕是面试我也建议先把暴力解写出来。它是最直接的“题意翻译”对每个位置 i遍历整个数组把所有j ! i的元素乘起来。Java 代码如下public int[] productExceptSelf(int[] nums) { int n nums.length; int[] answer new int[n]; for (int i 0; i n; i) { int product 1; for (int j 0; j n; j) { if (j ! i) { product * nums[j]; } } answer[i] product; } return answer; }稍微优化一点可以不用判断直接分成两段累乘省掉每次循环的if分支for (int i 0; i n; i) { int product 1; for (int j 0; j i; j) { product * nums[j]; } for (int j i 1; j n; j) { product * nums[j]; } answer[i] product; }两段累乘在时间量级上和带判断的版本一样但更贴合“除自己以外”的语义也方便和后面的左右乘积法对照。2.2 时间复杂度n 为 10^5 时会慢到什么程度暴力解的时间复杂度是 O(n²)。题目给出的数组最长可达 10⁵10⁵ 的平方是 10¹⁰这个量级的运算在一秒内基本不可能完成普通 JVM 每秒大概能执行 10⁸ 到 10⁹ 次简单整数运算10¹⁰ 次乘法必然超时。所以暴力解在 LeetCode 上无法通过但它依然有不可替代的价值。2.3 暴力解的三重价值第一验证你的题意理解。如果暴力输出的示例都对不上后面优化再漂亮也没用。第二作为对拍的“参考答案”。优化版本写完后用随机小数组分别跑暴力版和优化版逐一对比结果可以快速发现边界错误。第三面试表达。面试官想看的是“你能从朴素方案出发逐步意识到瓶颈并在提示或引导下优化”而不是直接背出最优解。我面试别人时候选人如果能先给出暴力解并说明“这版时间复杂度太高”再往下走印象分会好很多。3. 左右乘积数组把“整体乘积”拆成“左侧积 × 右侧积”3.1 前缀积与后缀积的递推关系定义两个辅助数组left[i]表示nums[0]到nums[i-1]的乘积也就是 i 左侧所有元素的乘积right[i]表示nums[i1]到nums[n-1]的乘积也就是 i 右侧所有元素的乘积。边界上left[0]没有任何左侧元素是空乘积约定为 1right[n-1]同理约定为 1。为什么空乘积是 1因为 1 是乘法的单位元任何数乘以 1 保持不变这样递推公式在边界处依然成立。递推关系非常自然left[i] left[i-1] * nums[i-1] right[i] right[i1] * nums[i1]以left为例从 i1 开始left[1] left[0] * nums[0] nums[0]left[2] left[1] * nums[1] nums[0] * nums[1]。一次正向遍历就能把所有位置的左侧积全部算好。right同理从 n-2 开始反向遍历即可。3.2 两个辅助数组的 Java 实现public int[] productExceptSelf(int[] nums) { int n nums.length; int[] left new int[n]; int[] right new int[n]; left[0] 1; for (int i 1; i n; i) { left[i] left[i - 1] * nums[i - 1]; } right[n - 1] 1; for (int i n - 2; i 0; i--) { right[i] right[i 1] * nums[i 1]; } int[] answer new int[n]; for (int i 0; i n; i) { answer[i] left[i] * right[i]; } return answer; }到这里时间复杂度已经降到 O(n)额外空间是 O(n)。这个版本在 LeetCode 上可以 AC很多人的刷题之旅也就停在了这一版。但它还有优化空间而且面试官大概率会追问。3.3 正确性依据与直观表格验证为什么left[i] * right[i]一定等于题目要求的乘积因为“除nums[i]之外的所有元素”这个集合恰好被nums[i]一分为二左边全部、右边全部。集合求积满足结合律和交换律先算左边的积、再算右边的积、最后乘在一起和“一次性把集合里所有数乘起来”在数学上是等价的。这个结论不看具体元素所以负数、0、重复数字都不影响。用[1,2,3,4]走一遍inums[i]left[i]right[i]answer[i]0112×3×424241213×41212231×2248341×2×3616和题目输出完全一致。这个表格也顺带说明了如果能把left或right中的一个数组“省掉”空间复杂度就能再降一档。4. 空间 O(1) 的终极优化answer 数组先写左积再被右积补全4.1 从“两个辅助数组”到“只用输出数组”上一节里answer[i]需要同时拿到left[i]和right[i]。如果保留两个辅助数组空间就是 O(n)。但仔细想一下left数组的作用只是把左侧积暂存下来等right也准备好之后做一次乘法。能不能让answer自己先扮演left的角色完全可以。第一遍从左往右扫描时直接把左侧积写进answer[i]answer[0] 1; for (int i 1; i n; i) { answer[i] answer[i - 1] * nums[i - 1]; }此时answer数组的内容就是left数组的内容辅助数组left被“合并”掉了。4.2 两遍扫描的核心逻辑与“不污染”的原因接着处理右侧积。维护一个变量right初始化为 1表示“从最右边开始累积的右侧乘积”。从i n-1一直扫到i 0每轮做两件事answer[i] answer[i] * right; right * nums[i];第一件事把当前答案补上右侧积第二件事更新right让它成为下一个位置i-1的右侧积。可能有人会担心answer里存的左侧积会不会在更新过程中被“污染”不会。关键在扫描方向是从右往左answer[i]被乘上right变成最终值之后后续循环不会再访问answer[i]而接下来要用的answer[i-1]仍保留着纯左侧积没有被碰过。所以“就地覆盖”是完全安全的。这个手法在算法里有一个更大的名字叫“原地复用前置结果”是空间优化的常见套路。如果还觉得绕可以用一个类比第一遍相当于每个人先在纸上写下“我左边所有人的乘积”第二遍从队伍最右边开始每个人手里拿着一个“右边所有人的乘积”的牌子挨个走到左边把牌子上的数和纸上的数相乘然后再把自己的数乘进牌子里传给下一个人。4.3 完整代码与手动走查完整实现public int[] productExceptSelf(int[] nums) { int n nums.length; int[] answer new int[n]; // 第一遍answer[i] 先存左侧积 answer[0] 1; for (int i 1; i n; i) { answer[i] answer[i - 1] * nums[i - 1]; } // 第二遍用滚动变量 right 补全右侧积 int right 1; for (int i n - 1; i 0; i--) { answer[i] answer[i] * right; right * nums[i]; } return answer; }用[1,2,3,4]手动走查一遍。第一遍结束后answer [1, 1, 2, 6]第二遍right 1 i 3: answer[3] 6 × 1 6 right 1 × 4 4 i 2: answer[2] 2 × 4 8 right 4 × 3 12 i 1: answer[1] 1 × 12 12 right 12 × 2 24 i 0: answer[0] 1 × 24 24 right 24 × 1 24最终answer [24, 12, 8, 6]正确。时间复杂度 O(n)两遍线性扫描额外空间 O(1)answer是题目要求的输出不计入额外空间。这就是这道题在 Java 下的标准最优解。LeetCode 官方题解里的“空间复杂度 O(1)”写法和这个基本一致。5. 边界条件与面试追问零元素、单元素、溢出、除法变体5.1 零元素的处理带 0 的用例是[-1,1,0,-3,3]期望输出[0,0,9,0,0]。用最终优化版跑一次第一遍算出左侧积第二遍从右往左乘右侧积整个过程中 0 只是参与乘法的一个普通元素把某些位置的积变成 0不需要任何特殊分支。这也是左右乘积法比除法方案优雅的地方——它把“0 的分布”这个问题直接消解掉了。5.2 单元素与空数组的防御性写法LeetCode 的数据保证了nums.length 2所以刷题时可以不用管单元素情况。但面试时主动提边界能加分工程上更需要防御。一个稳妥写法public int[] productExceptSelf(int[] nums) { if (nums null || nums.length 0) { return new int[0]; } if (nums.length 1) { return new int[]{1}; // 空乘积约定为 1 } // 正式逻辑... }注意 n1 时按定义是“除 nums[0] 外所有元素的乘积”也就是空乘积 1。很多人在这一步会写成返回原数组语义上其实是错的。5.3 如果面试官允许你用除法这是一个很常见的追问。允许除法时思路换成“总乘积剔除当前元素”public int[] productExceptSelfWithDivision(int[] nums) { int n nums.length; int[] answer new int[n]; int total 1; int zeroCount 0; int zeroIndex -1; for (int i 0; i n; i) { if (nums[i] 0) { zeroCount; zeroIndex i; } else { total * nums[i]; } } if (zeroCount 2) { // 所有答案都是 0 return answer; } if (zeroCount 1) { answer[zeroIndex] total; return answer; } for (int i 0; i n; i) { answer[i] total / nums[i]; } return answer; }分类的依据是 0 的个数没有 0直接除恰好一个 0只有那个位置是“其余元素的乘积”其他位置全是 0至少两个 0全部是 0。这个版本的代码明显比左右乘积法啰嗦而且每一步都要考虑除零风险。这恰好能解释为什么题目要禁除法——不是不能用而是“总乘积 除法”这一思路在数据分布稍微复杂一点时就会变得脆弱远不如“左右拆分”干净。5.4 整型溢出的隐患与稳妥做法题目保证最终答案在 32 位有符号整数范围内所以主流题解的int写法可以直接通过。但严格来说中间过程不一定安全例如数组里某个位置的右侧积为 0最终答案会变成 0而左侧积本身可能非常大。如果两侧的中间乘积超过Integer.MAX_VALUE用int累积就会溢出。LeetCode 官方的测试数据没有触发这类情况但在工程思维里这是一个不能忽略的风险点。稳妥的做法是把累积变量换成longlong[] answer new long[n]; // 或者内部使用 long 累积最后强转 int如果题目要求返回int[]可以在最后强转并在注释里说明依赖题目保证。更极端的场景元素值巨大、结果超过 64 位就只能用BigInteger或者取模运算那就是另一套考点了。面试时提到这一点会显得你不是只会抄题解。5.5 面试官真正想看的三件事我面过不少候选人出这题时主要看三点第一能不能从“全局除法”切换到“左右拆分”这是思路的拐点第二能不能在没有提示的情况下完成空间优化这反映你对“数组被复用后值的含义”是否敏感第三能不能主动讨论 0 和溢出这是考察工程意识。如果你只是想背代码这三关都过不了。所以刷题的时候建议把暴力、双数组、单变量三个版本都亲手写一遍把差异想透。6. 把“前缀积/后缀积”的套路迁移到其他地方6.1 前缀和与前后缀信息的家族题目这道题的核心手法是“预计算前缀/后缀信息再在 O(1) 时间内回答每个位置的问题”。前缀思想在 LeetCode 里非常常见最基础的是前缀和LeetCode 303 区域和检索preSum[i]表示前 i 个元素之和区间和sum[left, right]就能用preSum[right1] - preSum[left]得到LeetCode 724 寻找数组的中心下标求一个位置使左右和相等可以先求总和再从左往右累加判断leftSum total - leftSum - nums[i]LeetCode 560 和为 K 的子数组把前缀和存进哈希表一趟遍历完成统计。和本题关系最紧密的是 724它同样需要“左半边信息 右半边信息”的组合。掌握了“排除自身”这种套路这些题看起来会有一层相同的底色。6.2 工程场景中的“排除自身”统计很多人觉得算法题和业务开发是两座孤岛。我自己在数据相关项目里见过这类问题的工程版比如风控系统要计算某个交易指标时需要判断“如果把当前样本剔除整体的均值或方差会不会发生显著变化”这时就需要快速得到“除当前样本外的聚合值”。数据量小直接双重循环无所谓但到百万级样本就必须用前缀/后缀累计值配合运算。再比如推荐系统里给物品打分做归一化时有时也需要每个位置排除自身后的分母。前缀累积这个思路在离线计算和流式计算里都有对应实现。如果只记住一句话我的总结是当一个数组里每个位置的答案都依赖于“其他位置”的整体信息时先看看能不能把整体拆成“左侧 右侧”分别预计算再合并。这个想法从这道题出发可以延伸到一大片题目和真实系统。我在刷题和面试里反复和这道题打交道最深的感觉是最优解的记忆成本其实很低难的是理解它为什么这样设计。建议你照着三个版本各写一遍再用随机数组把暴力版和最终版跑一个对拍确认全绿之后这道题才算真正吃透了。后续再遇到任何“排除自身”型的问题你会第一时间想起这个左右拆分的套路。
)
