LeetCode 题解：除自身以外数组的乘积
在刷 LeetCode 的过程中，“除自身以外数组的乘积” 是一道经典的数组类题目，这道题不仅考察对数组遍历的理解，还要求在时间和空间复杂度上做到最优。今天就来分享这道题的高效解法，核心思路是通过两次遍历、利用两个变量分别记录左右侧乘积，实现时间复杂度 O (n)、空间复杂度 O (1)的最优解。
题目描述
给你一个长度为 n 的整数数组 nums，返回一个数组 ans，其中 ans [i] 等于 nums 中除 nums [i] 之外其余所有元素的乘积。要求不能使用除法，且在 O (n) 时间复杂度内完成，额外空间复杂度尽可能优化（除了答案数组外，仅使用常数级空间）。
解题思路
核心思想是拆分乘积计算：将 “除当前元素外所有元素的乘积” 拆分为 “当前元素左侧所有元素的乘积 × 当前元素右侧所有元素的乘积”，通过两次遍历分别计算左右侧乘积，最终合并结果。
具体步骤：
- 定义两个变量
left和right，分别表示当前元素左侧所有元素的乘积、右侧所有元素的乘积，初始值均为 1（因为单个元素的左侧 / 右侧无元素，乘积为 1）。 - 定义答案数组
ans，长度与输入数组nums一致。 - 左到右遍历：遍历每个元素时，先将当前
left（即该元素左侧所有元素的乘积）存入ans[i]，再更新left为left × nums[i]（为下一个元素的左侧乘积做准备）。 - 右到左遍历：遍历每个元素时，将
ans[i]（左侧乘积）乘以当前right（右侧乘积），得到最终的 “除自身外所有元素的乘积”，再更新right为right × nums[i]（为前一个元素的右侧乘积做准备）。 - 遍历完成后，
ans数组即为最终结果。
复杂度分析
- 时间复杂度：O (n)，仅需两次遍历数组，n 为数组长度。
- 空间复杂度：O (1)，除了存储结果的
ans数组外，仅使用了left和right两个常数级变量（题目通常允许忽略答案数组的空间消耗）。
Java 代码
class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; // 定义答案数组 int[] ans = new int[n]; // 第一步：左到右遍历，计算每个元素左侧所有元素的乘积 int left = 1; for (int i = 0; i < n; i++) { // 先将左侧乘积存入ans[i] ans[i] = left; // 更新left，为下一个元素的左侧乘积做准备 left *= nums[i]; } // 第二步：右到左遍历，计算右侧乘积并与左侧乘积相乘 int right = 1; for (int i = n - 1; i >= 0; i--) { // 左侧乘积 × 右侧乘积 = 最终结果 ans[i] *= right; // 更新right，为前一个元素的右侧乘积做准备 right *= nums[i]; } return ans; } } 代码解析
- 初始化阶段：
int n = nums.length;获取数组长度，用于定义答案数组和遍历边界。int[] ans = new int[n];初始化答案数组，存储最终结果。
- 左到右遍历：
left初始为 1，因为第一个元素左侧无元素，乘积为 1。- 遍历到第
i个元素时，先把left（左侧乘积）赋值给ans[i]，再让left乘以当前元素nums[i]，这样遍历结束后，ans[i]存储的是第i个元素左侧所有元素的乘积。
- 右到左遍历：
right初始为 1，因为最后一个元素右侧无元素，乘积为 1。- 遍历到第
i个元素时，将ans[i]（左侧乘积）乘以right（右侧乘积），得到该位置的最终结果；再让right乘以当前元素nums[i]，为前一个元素的右侧乘积做准备。
示例验证
以输入 nums = [1,2,3,4] 为例：
- 左到右遍历后，
ans = [1, 1, 2, 6]（分别对应每个元素左侧乘积：1、1、1×2、1×2×3）。 - 右到左遍历：
- i=3：
ans[3] = 6 × 1 = 6，right = 1×4=4； - i=2：
ans[2] = 2 × 4 = 8，right = 4×3=12； - i=1：
ans[1] = 1 × 12 = 12，right = 12×2=24； - i=0：
ans[0] = 1 × 24 = 24，right = 24×1=24；
- i=3：
- 最终
ans = [24,12,8,6]，符合 “除自身外所有元素乘积” 的结果。
总结
这道题的核心是拆分乘积计算，通过两次遍历分别处理左右侧乘积，避免了使用除法和额外的数组存储左右乘积，是空间优化的经典思路。关键点总结：
- 利用两个变量
left和right分别记录当前元素的左右侧乘积，替代额外数组，实现空间复杂度 O (1)； - 两次遍历的顺序（先左后右）保证了每个位置的乘积能被逐步计算；
- 遍历过程中 “先赋值后更新” 的逻辑，确保了当前元素不会被包含到自身的左右乘积中。
这种思路不仅适用于这道题，也可以迁移到其他需要 “左右侧遍历” 的数组类题目中，希望能帮助大家理解和掌握～
