- 难度：
中等 - 本题涉及算法：
- 思路：
乘积 = 左边乘积 * 右边乘积 - 类似题型:
题目 238. 除自身以外数组的乘积
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
方法一 乘积 = 左边乘积 * 右边乘积
- 解题思路：
- 第一印象，想用除法，$（所有数乘积/nums[i]）$ ，同时需要对
0做判断； - 第二印象，想试试滑动窗口，但是复杂度会变成 $n^2$；
- 沿着滑动窗口的思路，改良下得出
乘积 = 当前数左边的乘积 * 当前数右边的乘积
- 第一印象，想用除法，$（所有数乘积/nums[i]）$ ，同时需要对
- 复杂度分析：
- 时间复杂度：$O(n)$， $n$ 代表数组的长度
- 空间复杂度：$O(1)$， 排除返回数组空间为 $n$
java
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] res = new int[nums.length]; // 初始化长度为 nums.length 的数组
int r = 1; // 右边的乘积
for(int i=nums.length-1;i>=0;i--) {
r *= nums[i];
res[i] = r;
}
int l = 1; //左边的乘积
for(int i = 0;i<nums.length-1;i++) {
res[i] = l * res[i+1];
l *= nums[i];
}
res[nums.length-1] = l;
return res;
}
}
python
class Solution(object):
def productExceptSelf(self, nums):
res = [1] * len(nums) # 初始化长度为 le(nums) 的数组
r = 1 # 右边的乘积
for i in range(len(nums)-1,-1,-1):
r *= nums[i]
res[i] = r
l = 1 # 左边的乘积
for i in range(len(nums)-1):
res[i] = res[i+1] * l
l *= nums[i]
res[-1] = l
return res
PREVIOUS365. 水壶问题
NEXT229. 求众数 II