题目描述
给你一个长度为 n 的整数数组 nums,返回一个数组 ans,其中 ans[i] 等于 nums 中除 nums[i] 之外其余所有元素的乘积。要求不能使用除法,且在 O(n) 时间复杂度内完成,额外空间复杂度尽可能优化(除了答案数组外,仅使用常数级空间)。
解题思路
核心思想是拆分乘积计算:将'除当前元素外所有元素的乘积'拆分为'当前元素左侧所有元素的乘积 × 当前元素右侧所有元素的乘积',通过两次遍历分别计算左右侧乘积,最终合并结果。
具体步骤:
- 定义两个变量
left和right,分别表示当前元素左侧所有元素的乘积、右侧所有元素的乘积,初始值均为 1。 - 定义答案数组
ans,长度与输入数组nums一致。 - 左到右遍历:遍历每个元素时,先将当前
left存入ans[i],再更新left为left × nums[i]。 - 右到左遍历:遍历每个元素时,将
ans[i]乘以当前right,得到最终结果,再更新right为right × nums[i]。 - 遍历完成后,
ans数组即为最终结果。
复杂度分析
- 时间复杂度:O(n),仅需两次遍历数组。
- 空间复杂度:O(1),仅使用了
left和right两个常数级变量。
Java 代码
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
int left = 1;
for (int i = 0; i < n; i++) {
ans[i] = left;
left *= nums[i];
}
int right = 1;
for (int i n - ; i >= ; i--) {
ans[i] *= right;
right *= nums[i];
}
ans;
}
}


