前言上一篇我们刚刷完轮转数组。那道题其实挺典型一开始最容易想到暴力移动后面逐渐发现可以通过反转数组完成优化。说白了轮转数组更偏向于“如何优化操作过程”但当我刷到238. 除自身以外数组的乘积时明显感觉难度又往上走了一层。因为这次不再只是模拟过程而是开始真正要求你拆结构、找规律、避免重复计算。刚看到题目时我第一反应还是“总乘积算出来然后除自己不就行了”结果熟悉的限制来了禁止除法时间复杂度 O(n)只能说 LeetCode 太懂大家会偷懒但看到题目要求不能用除法时间复杂度 O(n)当时我就知道这题肯定没表面那么简单。这道题特别像 LeetCode 里那种看着简单实际很考察思维转换。也是我第一次真正感受到“前缀思想”到底有多重要。 题目速览LeetCode 238. 除自身以外数组的乘积给你一个数组nums返回一个新数组answeranswer[i] nums中除了nums[i]之外所有元素的乘积示例输入: nums [1,2,3,4] 输出: [24,12,8,6] 我的第一反应大部分人都会这样想方法一总乘积 / 当前值比如总乘积 1×2×3×4 24那么24 / 1 2424 / 2 1224 / 3 824 / 4 6看起来完美。❌ 但问题来了题目明确禁止除法。而且如果数组里有 0[1,2,0,4]直接炸掉。所以这条路行不通。 真正解法前缀积 后缀积刚开始我其实没太想明白后来画图后突然通了。比如对于位置 i我们其实只需要左边所有数的乘积 × 右边所有数的乘积举例nums [1,2,3,4]对于数字 3下标2结果 1 × 2 × 4 8也就是左边乘积 × 右边乘积✅ 思路一下就清晰了第一步提前算好每个位置左边所有元素乘积第二步再反向遍历乘上右边所有元素乘积✨ 解法代码最好理解版本class Solution { public int[] productExceptSelf(int[] nums) { int n nums.length; int[] left new int[n]; int[] right new int[n]; int[] ans new int[n]; // left[i] 表示 i 左边所有元素乘积 left[0] 1; for (int i 1; i n; i) { left[i] left[i - 1] * nums[i - 1]; } // right[i] 表示 i 右边所有元素乘积 right[n - 1] 1; for (int i n - 2; i 0; i--) { right[i] right[i 1] * nums[i 1]; } // 最终结果 for (int i 0; i n; i) { ans[i] left[i] * right[i]; } return ans; } } 执行过程拆解nums[1,2,3,4]left数组[1,1,2,6]解释left[0] 1left[1] 1left[2] 1×2left[3] 1×2×3right数组[24,12,4,1]最终ans[i] left[i] × right[i]结果[24,12,8,6]⚡ 更进一步空间优化面试更喜欢后来发现其实right数组根本没必要存。用一个变量就行。class Solution { public int[] productExceptSelf(int[] nums) { int n nums.length; int[] ans new int[n]; // 先存左边乘积 ans[0] 1; for (int i 1; i n; i) { ans[i] ans[i - 1] * nums[i - 1]; } // 再动态乘右边乘积 int right 1; for (int i n - 1; i 0; i--) { ans[i] * right; right * nums[i]; } return ans; } } 这题我学到的东西刷完之后我发现这题真正难的不是代码而是“如何避免重复计算”你不是每次都重新算一遍而是提前把信息存起来。这其实就是很多高频算法题的核心思想空间换时间。⚠️ 易错点总结❌ 不要忘记初始化ans[0] 1; right 1;❌ 不要想着偷懒用除法面试官基本就看你有没有理解前缀思想。 一句话总结这题核心每个位置的答案 左边贡献 × 右边贡献 面试收尾直接背“这道题本质上是通过前缀积和后缀积拆分每个位置的乘积贡献避免重复遍历从而在 O(n) 时间内完成结果计算并可进一步将空间复杂度优化到 O(1)。”