除自身以外数组的乘积 - Java 实现

题目描述

给你一个长度为 n 的整数数组 nums，返回一个数组 ans，其中 ans[i] 等于 nums 中除 nums[i] 之外其余所有元素的乘积。要求不能使用除法，且在 O(n) 时间复杂度内完成，额外空间复杂度尽可能优化（除了答案数组外，仅使用常数级空间）。

解题思路

核心思想是拆分乘积计算：将'除当前元素外所有元素的乘积'拆分为'当前元素左侧所有元素的乘积 × 当前元素右侧所有元素的乘积'，通过两次遍历分别计算左右侧乘积，最终合并结果。

具体步骤：

1. 定义两个变量 left 和 right，分别表示当前元素左侧所有元素的乘积、右侧所有元素的乘积，初始值均为 1。
2. 定义答案数组 ans，长度与输入数组 nums 一致。
3. 左到右遍历：遍历每个元素时，先将当前 left 存入 ans[i]，再更新 left 为 left × nums[i]。
4. 右到左遍历：遍历每个元素时，将 ans[i] 乘以当前 right，得到最终结果，再更新 right 为 right × nums[i]。
5. 遍历完成后，ans 数组即为最终结果。

复杂度分析

• 时间复杂度：O(n)，仅需两次遍历数组。
• 空间复杂度：O(1)，仅使用了 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] = left;
            left *= nums[i];
        }
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] *= right;
            right *= nums[i];
        }
        return ans;
    }
}

代码解析

1. 初始化阶段：获取数组长度，初始化答案数组。
2. 左到右遍历：left 初始为 1，遍历到第 i 个元素时，先把 left 赋值给 ans[i]，再让 left 乘以当前元素 nums[i]。
3. 右到左遍历：right 初始为 1，遍历到第 i 个元素时，将 ans[i] 乘以 right，再让 right 乘以当前元素 nums[i]。

示例验证

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

• 左到右遍历后，ans = [1, 1, 2, 6]。
• 右到左遍历：
  • 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；
• 最终 ans = [24,12,8,6]。

总结

这道题的核心是拆分乘积计算，通过两次遍历分别处理左右侧乘积，避免了使用除法和额外的数组存储左右乘积，是空间优化的经典思路。关键点总结：

1. 利用两个变量 left 和 right 分别记录当前元素的左右侧乘积，替代额外数组，实现空间复杂度 O(1)；
2. 两次遍历的顺序保证了每个位置的乘积能被逐步计算；
3. 遍历过程中'先赋值后更新'的逻辑，确保了当前元素不会被包含到自身的左右乘积中。