DeepSeek LeetCode 238. 除了自身以外数组的乘积 Java实现

LeetCode 238. 除了自身以外数组的乘积

题目描述

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

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

要求：不要使用除法，且在 O(n) 时间复杂度内完成。

解题思路

由于不能使用除法，可以采用 左右乘积 的方式：

· answer[i] = nums[0…i-1] 的乘积 × nums[i+1…n-1] 的乘积
· 先从左到右遍历，计算每个位置左侧所有元素的乘积，存入结果数组
· 再从右到左遍历，用一个变量 right 维护右侧所有元素的乘积，乘到结果数组对应位置

这样只需常数级额外空间（输出数组不计入）。

Java 实现

classSolution{publicint[]productExceptSelf(int[]nums){intn=nums.length;int[]res=newint[n];// 1. 从左到右：res[i] 表示 nums[i] 左侧所有元素的乘积res[0]=1;for(inti=1;i<n;i++){res[i]=res[i-1]*nums[i-1];}// 2. 从右到左：用 right 维护右侧所有元素的乘积intright=1;for(inti=n-1;i>=0;i--){res[i]*=right;// 左侧乘积 × 右侧乘积right*=nums[i];// 更新右侧乘积}returnres;}}

执行示例

输入：nums = [1, 2, 3, 4]

步骤 结果数组 res
初始化 [1, 0, 0, 0]
从左到右计算左侧乘积 [1, 1, 2, 6]
从右到左乘上右侧乘积 [24, 12, 8, 6]

最终输出：[24, 12, 8, 6]

复杂度分析

指标 复杂度
时间复杂度 O(n)
空间复杂度 O(1)（不计算返回数组）

关键点

1. 不使用除法：避免处理除数为 0 的特殊情况。
2. 两次遍历：第一次存左侧乘积，第二次乘上右侧乘积。
3. 空间优化：直接复用返回数组存储左侧乘积，再用一个变量维护右侧乘积，无需额外数组。
4. 边界情况：数组长度为 2 时同样适用，结果数组每个位置都是另一个元素的值。