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

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

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;
}