首页leetcode hot 100 除自身以外数组的乘积 java

leetcode hot 100 除自身以外数组的乘积 java

时间: 2025-04-27 15:55:48 浏览: 22

### LeetCode Hot 100 '除自身以外数组的乘积' Java 解决方案对于给定的一个整数数组 `nums`，目标是构建一个新的数组 `answer`，使得 `answer[i]` 是除了 `nums[i]` 外所有元素的乘积。此问题可以通过两次遍历实现，在不使用额外空间的情况下完成计算。 #### 方法概述通过两个方向的扫描来解决问题：一次正向扫描用于累积左侧部分的结果；另一次反向扫描则更新右侧部分并最终形成完整的解法[^2]。 #### 正向扫描初始化一个变量 `leftProduct` 来保存当前索引左边所有数字相乘得到的结果，并将其赋值给新创建的答案列表对应位置上。随着迭代过程不断更新这个累加器以便后续使用。 ```java public class Solution { public int[] productExceptSelf(int[] nums) { int length = nums.length; int[] answer = new int[length]; // 初始化为1是因为任何数与1相乘都等于其本身 int leftProduct = 1; for (int i = 0; i < length; ++i){ answer[i] = leftProduct; leftProduct *= nums[i]; } ``` #### 反向扫描接着从右至左再次遍历输入数组的同时维护另一个临时变量 `rightProduct` 记录右边元素连乘结果。每一步都将之前存储好的左侧产品乘以此时获得的新因子存入答案数组相应下标的格子内。 ```java int rightProduct = 1; for (int i = length - 1; i >= 0; --i){ answer[i] *= rightProduct; rightProduct *= nums[i]; } return answer; } } ``` 这种方法不仅满足题目要求的空间复杂度 O(1)，而且时间效率也达到了最优水平——线性的O(n)。

阅读全文