LeetCode 题解工作台
除了自身以外数组的乘积
给你一个整数数组 nums ，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法， 且在 O(n) 时间复杂度内完…
2
题型
9
代码语言
3
相关题
当前训练重点
中等 · 前缀和
答案摘要
我们定义两个变量 和 ，分别表示当前元素左边所有元素的乘积和右边所有元素的乘积。初始时 , 。定义一个长度为 的答案数组 。 我们先从左到右遍历数组，对于遍历到的第 个元素，我们用 更新 ，然后 乘以 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 前缀和 题型思路
题目描述
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums =[1,2,3,4]输出:[24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]
提示：
2 <= nums.length <= 105-30 <= nums[i] <= 30- 输入 保证 数组
answer[i]在 32 位 整数范围内
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
解题思路
方法一：两次遍历
我们定义两个变量 和 ，分别表示当前元素左边所有元素的乘积和右边所有元素的乘积。初始时 , 。定义一个长度为 的答案数组 。
我们先从左到右遍历数组，对于遍历到的第 个元素，我们用 更新 ，然后 乘以 。
然后，我们从右到左遍历数组，对于遍历到的第 个元素，我们更新 为 ，然后 乘以 。
遍历结束后，返回答案数组 。
时间复杂度 ，其中 是数组 的长度。忽略答案数组的空间消耗，空间复杂度 。
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [0] * n
left = right = 1
for i, x in enumerate(nums):
ans[i] = left
left *= x
for i in range(n - 1, -1, -1):
ans[i] *= right
right *= nums[i]
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate's ability to efficiently use prefix and suffix products to avoid unnecessary calculations.
- question_mark
Understanding of optimizing space complexity, especially avoiding extra arrays for prefix and suffix products.
- question_mark
Clarity in explaining how to achieve the desired result in O(n) time without using division.
常见陷阱
外企场景- error
Incorrectly using division to calculate the product, which violates the problem's constraints.
- error
Failing to consider edge cases like zeros in the input array, which may lead to incorrect results if not handled properly.
- error
Not understanding the importance of optimizing space usage by avoiding unnecessary auxiliary arrays.
进阶变体
外企场景- arrow_right_alt
Handling larger input arrays, where O(n) time complexity and O(1) space complexity are crucial.
- arrow_right_alt
Considering cases with multiple zeros in the array, which will require special handling to avoid incorrect products.
- arrow_right_alt
Implementing a solution that doesn't require additional memory for prefix and suffix arrays but still ensures efficiency.