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

这是一个经典的数组问题，需要在不使用除法的情况下，以O(n)时间复杂度解决。我们可以通过前缀乘积和后缀乘积的方法高效解决。

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];

        // 第一步：计算每个位置左侧所有元素的乘积
        answer[0] = 1; // 第一个元素左侧没有元素，设为1
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i-1] * nums[i-1];
        }

        // 第二步：计算右侧乘积并直接乘到结果中
        int rightProduct = 1; // 用于记录右侧元素的累积乘积
        for (int i = n - 1; i >= 0; i--) {
            answer[i] = answer[i] * rightProduct;
            rightProduct = rightProduct * nums[i];
        }

        return answer;
    }
}

算法解析：

1. 核心思路：

   • 将每个位置的乘积分解为两部分：左侧所有元素的乘积和右侧所有元素的乘积
   • 最终结果 = 左侧乘积 × 右侧乘积

2. 算法步骤：

   • 第一遍遍历（从左到右）：计算每个位置左侧所有元素的乘积
     • answer[i] 存储 nums[0] × nums[1] × ... × nums[i-1]
   • 第二遍遍历（从右到左）：计算右侧乘积并直接与左侧乘积相乘
     • 使用变量 rightProduct 动态维护右侧元素的累积乘积
     • 将 answer[i] 乘以 rightProduct 得到最终结果

3. 复杂度分析：

   • 时间复杂度：O(n)，仅需两次线性遍历
   • 空间复杂度：O(1)（不考虑输出数组），只使用了一个额外变量

4. 示例演示（nums = [1,2,3,4]）：

   • 第一遍后：answer = [1, 1, 2, 6]（左侧乘积）
   • 第二遍过程：
     • i=3: answer[3]=6×1=6, rightProduct=1×4=4
     • i=2: answer[2]=2×4=8, rightProduct=4×3=12
     • i=1: answer[1]=1×12=12, rightProduct=12×2=24
     • i=0: answer[0]=1×24=24, rightProduct=24×1=24
   • 最终结果：[24,12,8,6]

5. 优势：

   • 不使用除法，避免了除零错误
   • 时间复杂度为O(n)，满足题目要求
   • 空间效率高，只使用了常数级额外空间