LC238
除自身以外数组的乘积
前缀积 · 除自身外乘积可视化:前缀和/积nums=[1,2,3,4],输出 [24,12,8,6] 不用除法。
时间 O(n)空间 O(1)
题目1 / 12
题目与输入建立输入、目标与算法心智
答案[i]=左积×右积
正在加载算法场景...
当前发生了什么
nums=[1,2,3,4],输出 [24,12,8,6] 不用除法。
机器状态
prefix、suffix、结果数组。
为什么正确
前缀积+后缀积;或输出数组当前缀再倒序乘后缀 O(1) 空间。
不变量
ans[i]=prefix[i-1]*suffix[i+1]。
面试怎么说
两次扫描 prefix/suffix O(n)/O(1) 额外。
人类输入
nums=[1,2,3,4],输出 [24,12,8,6] 不用除法。
机制
前缀积+后缀积;或输出数组当前缀再倒序乘后缀 O(1) 空间。
机器状态
prefix、suffix、结果数组。
可观察结果
ans[i]=除 i 外全体乘积。
不变量
- · ans[i]=prefix[i-1]*suffix[i+1]。
常见误区
- · 直接用除法遇 0 麻烦且题目可能限制。
迁移练习
- · LC42 接雨水
- · LC560 和为 K
面试怎么答
两次扫描 prefix/suffix O(n)/O(1) 额外。