前缀和
先用后缀积填充答案数组，再用一个变量维护前缀积，从左到右乘进去，得到除自身以外的乘积。除返回数组外只用了常数空间。
时间复杂度：
空间复杂度：（返回数组不计入额外空间）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
ans[n - 1] = 1;
for (int i = n - 2; i >= 0; --i) {
ans[i] = ans[i + 1] * nums[i + 1];
};
int pre = 1;
for (int i = 0; i < n; ++i) {
ans[i] *= pre;
pre *= nums[i];
}
return ans;
}
}
|