#238
Medium
前缀和

Product of Array Except Self

返回除自身以外所有元素乘积组成的数组。

ArrayPrefix Sum

题目定位

虽然不是求和,但思路和前缀/后缀分解完全一样:每个位置答案等于左侧乘积乘右侧乘积。

关键观察

只要先算左侧乘积,再从右边扫一遍,就完全不需要除法。

目标复杂度

O(n) / O(1) extra

这题的解法思路怎么拆

1

虽然不是求和,但思路和前缀/后缀分解完全一样:每个位置答案等于左侧乘积乘右侧乘积。

2

只要先算左侧乘积,再从右边扫一遍,就完全不需要除法。

3

先定义累计状态代表什么。

4

一趟扫描构造前缀。

参考实现

Python
# Generic pattern template
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
    prefix[i + 1] = prefix[i] + value

range_sum = prefix[r + 1] - prefix[l]

常见坑点

warning

上来就用除法,结果在 0 场景下失效。

warning

额外分配完整左右数组,其实可以进一步优化。

高频追问

为什么从右往左再扫一遍就能省掉一个数组?

如果数组里有多个 0,结果会怎样?

继续刷相关题

先把 前缀和 这个模式刷成体系,再去做更难变体。

view_week回到模式页
LeetCode 238. Product of Array Except Self 题解思路 | Interview AiBox