力扣hot100-238.除自身以外数组的乘积-前缀积后缀积详解

LeetCode 238. 除自身以外数组的乘积前缀积 后缀积详解1. 这道题属于什么算法思想这题主要归类为数组 / 前缀积 后缀积它和“前缀和”思想类似但这里做的不是加法而是乘法。题目中每个位置的答案都由两部分组成当前位置左边所有元素的乘积。 当前位置右边所有元素的乘积。把这两部分相乘就得到“除自身以外数组的乘积”。2. 这道题到底在问什么题目要求返回数组answer满足answer[i] 等于 nums 中除了 nums[i] 之外其余所有元素的乘积。例如nums [1, 2, 3, 4]结果是answer[0] 2 * 3 * 4 24 answer[1] 1 * 3 * 4 12 answer[2] 1 * 2 * 4 8 answer[3] 1 * 2 * 3 6因此answer [24, 12, 8, 6]题目还有两个限制1. 不允许使用除法。 2. 要在 O(n) 时间内完成。3. 为什么不能直接用总乘积除自身最直观的想法是先计算所有元素的总乘积total nums[0] * nums[1] * ... * nums[n - 1]然后answer[i] total / nums[i]但题目明确禁止使用除法。而且数组中可能有0。例如nums [1, 2, 0, 4]总乘积是0如果计算answer[2]会得到0 / 0这无法计算。因此要换一种不依赖除法的方法。4. 为什么不直接使用暴力解法可以直接使用暴力解法它是正确的。思路是对于每个下标i重新遍历整个数组跳过nums[i]把其余元素相乘。classSolution{publicint[]productExceptSelf(int[]nums){intnnums.length;int[]answernewint[n];for(inti0;in;i){intproduct1;for(intj0;jn;j){// 当前答案不能乘 nums[i] 自己。if(i!j){product*nums[j];}}answer[i]product;}returnanswer;}}例如nums [1, 2, 3, 4]计算answer[0]时需要计算2 * 3 * 4计算answer[1]时又需要计算1 * 3 * 4其中3 * 4这部分被重复计算了。随着数组变大左边和右边的很多乘积都会反复计算。时间复杂度是外层循环 n 次。 每次内层循环遍历 n 次。 总时间复杂度是 O(n^2)。题目明确要求在O(n)时间内完成因此暴力法不能作为最终提交解法。前缀积和后缀积的作用就是提前保存并复用这些重复乘积left[i] 保存 i 左边所有元素的乘积。 right[i] 保存 i 右边所有元素的乘积。于是每个答案只需answer[i] left[i] * right[i]不再需要为每个i重新扫描整个数组。5. 第一性原理每个答案由左边和右边组成对于nums[i]需要排除的只有它自己。数组中其余元素可以自然拆成两部分nums[i] 左边的元素。 nums[i] 右边的元素。因此answer[i] 左边所有元素的乘积 * 右边所有元素的乘积例如nums [1, 2, 3, 4] 下标: 0 1 2 3对于i 2nums[2] 3左边元素是1, 2右边元素是4所以answer[2] (1 * 2) * 4 8这就是整题核心每个位置不需要重新遍历整个数组只需要知道它左边的乘积和右边的乘积。6. 用 left 和 right 两个数组直接表达思路定义left[i]nums[i] 左边所有元素的乘积。 right[i]nums[i] 右边所有元素的乘积。那么answer[i] left[i] * right[i]对于nums [1, 2, 3, 4]6.1 left 数组left[0]表示nums[0]左边所有元素的乘积。nums[0]左边没有元素因此left[0] 1为什么是1而不是0因为乘法中的空乘积定义为1。它的作用是保证没有左边元素时answer[0] 只由右边元素决定。 1 * 右边乘积 右边乘积。之后从左到右计算left[1] nums[0] 1 left[2] nums[0] * nums[1] 1 * 2 2 left[3] nums[0] * nums[1] * nums[2] 1 * 2 * 3 6所以left [1, 1, 2, 6]递推关系是left[i] left[i - 1] * nums[i - 1]原因是nums[i] 左边的元素 nums[i - 1] 左边的元素再加上 nums[i - 1] 自己。6.2 right 数组right[3]表示nums[3]右边所有元素的乘积。nums[3]右边没有元素因此right[3] 1之后从右到左计算right[2] nums[3] 4 right[1] nums[2] * nums[3] 3 * 4 12 right[0] nums[1] * nums[2] * nums[3] 2 * 3 * 4 24所以right [24, 12, 4, 1]递推关系是right[i] right[i 1] * nums[i 1]原因是nums[i] 右边的元素 nums[i 1] 右边的元素再加上 nums[i 1] 自己。6.3 合并 left 和 right最后逐个位置相乘answer[0] left[0] * right[0] 1 * 24 24 answer[1] left[1] * right[1] 1 * 12 12 answer[2] left[2] * right[2] 2 * 4 8 answer[3] left[3] * right[3] 6 * 1 6因此answer [24, 12, 8, 6]7. 用表格完整推导对于nums [1, 2, 3, 4]inums[i]left[i]左边乘积right[i]右边乘积answer[i]011242412112122324834616表格中每一行都满足answer[i] left[i] * right[i]8. 数组中有 0 时为什么仍然正确前缀积和后缀积不使用除法因此能自然处理0。例如nums [1, 2, 0, 4]正确答案应为answer [0, 0, 8, 0]解释answer[0] 2 * 0 * 4 0 answer[1] 1 * 0 * 4 0 answer[2] 1 * 2 * 4 8 answer[3] 1 * 2 * 0 0计算数组left [1, 1, 2, 0] right [0, 0, 4, 1]相乘[1 * 0, 1 * 0, 2 * 4, 0 * 1] [0, 0, 8, 0]结果正确。如果有两个或更多个0每个位置除自身外仍至少包含一个0所以所有答案都是0。前缀积和后缀积同样会自然得到这个结果。9. Java 代码完整注释classSolution{publicint[]productExceptSelf(int[]nums){intnnums.length;// left[i] 表示 nums[i] 左边所有元素的乘积。int[]leftnewint[n];// right[i] 表示 nums[i] 右边所有元素的乘积。int[]rightnewint[n];// answer[i] left[i] * right[i]。int[]answernewint[n];// nums[0] 左边没有元素空乘积为 1。left[0]1;// 从左到右计算每个位置左边的乘积。for(inti1;in;i){// nums[i] 左边的乘积// nums[i - 1] 左边的乘积 * nums[i - 1]。left[i]left[i-1]*nums[i-1];}// nums[n - 1] 右边没有元素空乘积为 1。right[n-1]1;// 从右到左计算每个位置右边的乘积。for(intin-2;i0;i--){// nums[i] 右边的乘积// nums[i 1] 右边的乘积 * nums[i 1]。right[i]right[i1]*nums[i1];}// 左边乘积 * 右边乘积就是除 nums[i] 之外所有元素的乘积。for(inti0;in;i){answer[i]left[i]*right[i];}returnanswer;}}10. 复杂度分析时间复杂度O(n)分别计算left、right和answer每一轮都只遍历数组一次总体仍是线性时间。空间复杂度O(n)除了题目要求返回的answer外还使用了left和right两个长度为n的数组。后续可以把left和right的信息复用到answer和一个普通变量中从而优化额外空间但这属于空间优化不是理解本题的必要前提。11. 总结这题属于数组 / 前缀积 后缀积核心公式是answer[i] left[i] * right[i]其中left[i] 表示 nums[i] 左边所有元素的乘积。 right[i] 表示 nums[i] 右边所有元素的乘积。left[0]和right[n - 1]都初始化为1因为两侧没有元素时空乘积应该是不改变结果的乘法单位元1。可以把整题记成一句话每个位置的答案等于它左边所有数的乘积乘以它右边所有数的乘积。