Interview:ProductExceptSelf

❓ 问题

给你一个整数数组 nums，你要生成一个新的数组 res，满足：
res[i] = 除了 nums[i] 之外，数组里所有其他数的乘积。

限制条件：

1. 不能用除法
2. 时间复杂度要 O(n)

🧠 思路总结

对任意一个位置i:
当前位置的结果 = 左边所有数的乘积 ✖️ 右边所有数的乘积

使用前缀 & 后缀法

✅ 代码（Java）

public static int[] productExceptSelf(int[] nums) {
  int[] res = new int[nums.length];
  // Left
  res[0] = 1; // it is the most left element
  for (int i = 1; i < nums.length; i++) {
      res[i] = res[i - 1] * nums[i - 1];
  }
  // Right
  int right = 1;
  for (int i = nums.length - 1; i >= 0; i--) {
      res[i] *= right;
      right *= nums[i];
  }
  return res;
}