当前位置：首页 > news >正文

LeetCode 热题 100 238. 除自身以外数组的乘积

news 来源：原创 2025/8/13 12:59:27

LeetCode 热题 100 | 238. 除自身以外数组的乘积

大家好，今天我们来解决一道经典的算法问题——除自身以外数组的乘积。这道题在 LeetCode 上被标记为中等难度，要求在不使用除法的情况下，计算数组中每个元素的乘积，其中每个元素的值是数组中除自身以外其余各元素的乘积。

问题描述

给你一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。

示例 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 <= 10^5
-30 <= nums[i] <= 30
输入保证数组 answer[i] 在 32 位整数范围内

解题思路

核心思想

前缀和后缀乘积：
- 使用两个数组 left 和 right 分别存储每个位置的前缀乘积和后缀乘积。
- left[i] 表示从数组开头到位置 i-1 的所有元素的乘积。
- right[i] 表示从位置 i+1 到数组末尾的所有元素的乘积。
- 最终结果 answer[i] 为 left[i] * right[i]。
优化空间复杂度：
- 可以直接在结果数组 answer 中计算前缀乘积，然后从后向前计算后缀乘积，从而避免使用额外的数组。

Python代码实现

class Solution:def productExceptSelf(self, nums: List[int]) -> List[int]:n = len(nums)answer = [1] * n# 计算前缀乘积left_product = 1for i in range(n):answer[i] = left_productleft_product *= nums[i]# 计算后缀乘积并更新结果right_product = 1for i in range(n - 1, -1, -1):answer[i] *= right_productright_product *= nums[i]return answer

代码解析

初始化：
- answer 数组初始化为长度为 n 的列表，所有值初始化为 1。
计算前缀乘积：
- 使用变量 left_product 记录当前元素之前的乘积。
- 遍历数组，更新 answer[i] 为 left_product，然后更新 left_product。
计算后缀乘积并更新结果：
- 使用变量 right_product 记录当前元素之后的乘积。
- 从后向前遍历数组，更新 answer[i] 为 answer[i] * right_product，然后更新 right_product。
返回结果：
- 最终结果存储在 answer 中。

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。只需要两次遍历数组。
空间复杂度：O(1)，直接在结果数组 answer 中计算，不使用额外的数组。

示例运行

示例 1

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

总结

通过前缀和后缀乘积的方法，我们可以高效地解决除自身以外数组的乘积问题。这种方法在 O(n) 时间复杂度内完成，并且只使用了常数级别的额外空间。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！