小哆啦解题记：如何计算除自身以外数组的乘积

小哆啦开始力扣每日一题的第十二天

https://leetcode.cn/problems/product-of-array-except-self/description/

《小哆啦解题记：如何计算除自身以外数组的乘积》

在一个清晨的阳光下，小哆啦坐在书桌前，思索着一道困扰已久的题目：

给定一个整数数组 nums，返回一个新的数组 answer，其中 answer[i] 等于 nums 中所有元素的乘积，除了 nums[i] 本身。

“这看起来不复杂吧？”小哆啦轻声自语，脑海里已经开始快速构建解题思路。看似简单的题目，背后却藏着优化的挑战。他决定从最基础的方法开始，尽管他并不期待它能跑得很快。

第一步：用双重循环解决问题

“最直接的方式是什么？”小哆啦问自己，随后他选择了使用两个嵌套的 for 循环来解决问题。对于每个元素，他都会计算数组中除了它自己以外的所有元素的乘积。

function productExceptSelf(nums: number[]): number[] {const n = nums.length;const answer: number[] = new Array(n);for (let i = 0; i < n; i++) {let product = 1;for (let j = 0; j < n; j++) {if (i !== j) {product *= nums[j];}}answer[i] = product;}return answer;
}

然而，当他输入一组较大的数字时，程序的速度开始变得异常缓慢。每次都要做两层循环，计算每个元素的乘积，这样的时间复杂度是 O(n2)) 。这显然不是一个高效的解法。

“嗯，看起来我得换个思路了。”小哆啦皱了皱眉头，开始思考如何避免重复计算。

第二步：寻找高效解法

小哆啦坐在书桌前，突然灵光一闪：“如果我计算出数组中每个元素左边的乘积，再计算出右边的乘积，然后结合起来，不就能避免重复计算吗？”这一瞬间，他感觉找到了答案。

他决定实现一个新思路：分别计算出每个元素左边和右边的乘积，然后将它们相乘。这样每个位置的答案就能得到，且时间复杂度将降到 O(n) 。

第三步：前缀积和后缀积的巧妙结合

小哆啦迅速动手实现这个新思路。首先，他计算出每个元素左边的所有元素的乘积（前缀积），然后计算每个元素右边的乘积（后缀积）。最后，将两者相乘即可得到最终的答案。

function productExceptSelf(nums: number[]): number[] {const n = nums.length;const answer: number[] = new Array(n).fill(1);// 计算前缀积let prefix = 1;for (let i = 0; i < n; i++) {answer[i] = prefix;prefix *= nums[i];}// 计算后缀积并更新结果let suffix = 1;for (let i = n - 1; i >= 0; i--) {answer[i] *= suffix;suffix *= nums[i];}return answer;
}

第四步：高效的实现，快速的运行

小哆啦再次运行代码。这一次，进度条飞速前进，几乎在眨眼之间就得到了正确的结果！

“太棒了！终于解决了。”小哆啦松了口气，心里充满了成就感。这种方法的时间复杂度是 O(n) ，比之前的暴力方法快得多，而且它只使用了常数空间存储前缀积和后缀积，空间复杂度为 O(1) ，除了结果数组。

第五步：胜利的微笑

回想这一路的艰难与突破，小哆啦感到十分满足。每一个程序员的成长，都是在一次次挑战中找到突破口的过程。从最初的双重循环到最后的前缀积和后缀积的优化，这不仅仅是一个简单的算法问题，而是一次智慧的提升。

他站起身来，望着窗外的蓝天，嘴角微微上扬：“未来的道路还很长，我会继续走下去，发现更多的优化和突破。”

---

结语：优化的思维，突破的力量

小哆啦的解题历程，给我们带来了深刻的启示：对于一个看似简单的问题，背后往往隐藏着对效率和优化的深刻理解。通过巧妙地运用前缀积和后缀积的方式，我们能够在 O(n) 的时间复杂度内高效地解决问题，避免了重复计算。

每次的挑战背后，都是对思维和能力的一次锤炼。当我们能够突破常规的思维方式，才能真正在算法的世界中找到属于自己的道路。