🔗 除自身以外数组的乘积

题目来源：238. 除自身以外数组的乘积 – 力扣（LeetCode）

---

📌 题目描述

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

• 要求：
  • 不能使用除法。
  • 在 O(n) 时间复杂度内完成。
  • 题目保证结果在 32 位整数范围内。

---

✅ 示例解析

示例 1：

• 输入：nums = [1,2,3,4]
• 输出：[24,12,8,6]
• 解释：
  • answer[0] = 2*3*4 = 24
  • answer[1] = 1*3*4 = 12
  • answer[2] = 1*2*4 = 8
  • answer[3] = 1*2*3 = 6

示例 2：

• 输入：nums = [-1,1,0,-3,3]
• 输出：[0,0,9,0,0]
• 解释：
  • 由于数组中存在 0，除 nums[2] 外的所有 answer[i] 都包含 0，故为 0。
  • answer[2] = (-1)*1*(-3)*3 = 9

---

⚠️ 提示

• 2 <= nums.length <= 10⁵
• -30 <= nums[i] <= 30
• 结果保证在 32 位整数范围内

---

💡 解法：前缀乘积 + 后缀乘积（两次遍历）—— O(n) 时间，O(1) 额外空间

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
      
        result[0] = 1;
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }
     
        int right = 1; 
        for (int i = n - 1; i >= 0; i--) {
            result[i] = result[i] * right; 
            right = right * nums[i]; 
        }
        
        return result;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n)
  • 第一次遍历计算前缀乘积：O(n)
  • 第二次遍历计算后缀乘积并更新结果：O(n)
  • 总体为线性时间。
• 空间复杂度：O(1)（不计返回数组）
  • result 数组为返回值，不计入额外空间。
  • 仅使用常数变量 right，满足题目对空间的要求。

---

🧩 解题思路

1. 核心思想：分解为前缀与后缀乘积
   对于任意位置 i，answer[i] = (nums[0] * ... * nums[i-1]) * (nums[i+1] * ... * nums[n-1])
   即：左边所有元素的乘积 × 右边所有元素的乘积
2. 两步走策略：
   • 步骤 1：计算前缀乘积
     使用 result 数组先存储每个位置 i 的左侧元素乘积。
     • result[0] = 1（左边无元素）
     • result[i] = result[i-1] * nums[i-1]（递推）
   • 步骤 2：计算后缀乘积并合并
     从右向左遍历，用变量 right 动态维护当前位置 i 的右侧元素乘积。
     • 初始 right = 1（最右元素右边无元素）
     • result[i] *= right：将右侧乘积乘到结果中
     • right *= nums[i]：更新 right，为下一轮（i-1）准备
3. 举例说明：
   对 nums = [1,2,3,4]：
   • 步骤 1 后：result = [1, 1, 2, 6]
     • result[1] = 1 * nums[0] = 1
     • result[2] = 1 * nums[1] = 2
     • result[3] = 2 * nums[2] = 6
   • 步骤 2 过程：
     • i=3: result[3] = 6 * 1 = 6, right = 1 * 4 = 4
     • i=2: result[2] = 2 * 4 = 8, right = 4 * 3 = 12
     • i=1: result[1] = 1 * 12 = 12, right = 12 * 2 = 24
     • i=0: result[0] = 1 * 24 = 24, right = 24 * 1 = 24
   • 最终 result = [24,12,8,6] ✅
4. 处理特殊情况（含 0）：
   • 该方法天然支持 0：
     • 若 nums[i] = 0，则 result[i] 只包含左侧乘积，右侧乘积由 right 传递
     • 如示例 2，right 在遇到 0 前为 3，在 i=2 时 result[2] = 2 * 3 = 6？
     • 实际过程会正确计算：right 会因 0 而变为 0，后续 result[i] 也变为 0，但 i=2 时 right 还未乘 0，因此能正确得到 9。