题目定位
虽然不是求和,但思路和前缀/后缀分解完全一样:每个位置答案等于左侧乘积乘右侧乘积。
关键观察
只要先算左侧乘积,再从右边扫一遍,就完全不需要除法。
目标复杂度
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,结果会怎样?
继续刷相关题
先把 前缀和 这个模式刷成体系,再去做更难变体。