【每日算法Day 4】除自身外数组的乘积：前/后缀和/积的妙用
Wallace Xu 2020-06-04 数组
# 题目链接
LeetCode 238. 除自身外数组的乘积 (opens new window)
# 题目描述
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。
# 示例
输入:
[1,2,3,4]
输出:
[24,12,8,6]
1
2
3
4
2
3
4
# 解题思路
记得之前做一道题目的时候为了避免额外的O(n)空间用到了前缀和，然而做这题的时候开始思想太僵只想到前缀积，没想到还有后缀积这种东西，一个元素的前缀积乘后缀积就是要求的结果。一遍从左向右遍历得到前缀积存在等长数组中，第二遍从右向左遍历得到后缀积直接乘以前缀积就能得到答案。
public int[] productExceptSelf(int[] nums) {
int[] result=new int[nums.length];
int k=1;
for (int i = 0; i < nums.length; i++) {
result[i]=k;//k临时存储当前前缀积并存在result[i]中
k*=nums[i];
}
k=1;
for (int i = nums.length - 1; i >= 0; i--) {
result[i]*=k;//这里是已有的前缀积乘以当前后缀积k
k*=nums[i];
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14