算法
Array Product Excluding Current
计算给定数组中不包含当前元素的乘积
题目要求
- 对给定的数组，计算每个位置
i除自身外所有数字的乘积 - 要求时间复杂度为
- 不能使用除法
思路
用两次遍历：
- 从左往右：构建前缀积
prefix，使result[i]先存左侧所有数的乘积。 - 从右往左：维护一个后缀积
suffix，把右侧的乘积再乘到result[i]上。
代码
function productExceptSelf(numbers: number[]): number[] {
const n = numbers.length;
const result = new Array(n).fill(0);
// 前缀积
let prefix = 1;
for (let i = 0; i < n; i++) {
result[i] = prefix;
prefix *= numbers[i];
}
// 后缀积
let suffix = 1;
for (let i = n - 1; i >= 0; i--) {
// 前缀积 * 后缀积
result[i] *= suffix;
suffix *= numbers[i];
}
return result;
}在 GitHub 上编辑
上次更新于