Product of Array Except Self

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

算法

前缀积数组 pre：
- pre[i] 表示 nums[0] 到 nums[i - 1] 的乘积
- 用于保存当前元素之前所有元素的乘积
后缀积变量 sub：
- 在第二次遍历时，通过一个变量动态记录从右到左的乘积（即 nums[i + 1] 到 nums[n - 1]的乘积）
- 每次更新 pre[i] 为 pre[i] * sub（计算结果数组），并更新 sub

复杂度分析

前缀积遍历一次，后缀积遍历一次，时间复杂度为 O(n)
使用了一个前缀积数组和一个后缀积变量，空间复杂度为 O(n)

C++ 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution
{
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();

        // 初始化前缀积数组
        std::vector<int> pre(n, 1);
        for (int i = 1; i < n; ++ i)
            pre[i] = pre[i - 1] * nums[i - 1];

        // 动态计算后缀积并更新结果
        int sub = 1;
        for (int i = n - 1; i >= 0; -- i)
        {
            pre[i] *= sub;
            sub *= nums[i];
        }

        return pre;
    }
};

Python 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
      n = len(nums)
      pre = [1] * n
      for i in range(1, n):
        pre[i] = pre[i - 1] * nums[i - 1]

      suffix = 1
      for i in range(n - 1, -1, -1):
        pre[i] *= suffix
        suffix *= nums[i]

      return pre

Go 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func productExceptSelf(nums []int) []int {
  n := len(nums)
  pre := make([]int, n)
  for i, _ := range pre {
    pre[i] = 1
  }

  for i := 1; i < n; i += 1 {
    pre[i] = pre[i - 1] * nums[i - 1]
  }

  suffix := 1
  for i := n - 1; i >= 0; i -= 1 {
    pre[i] *= suffix
    suffix *= nums[i]
  }

  return pre
}