面试经典150题 P238 除自身以外数组的乘积

---

时间轴

2025-10-05

init

---

题目：

P238 除自身以外数组的乘积

https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-interview-150

前缀和（Prefix Sum） 是算法中最常见、最实用的“预处理技巧”之一。它可以让你 快速求任意区间的和，从而极大地加速计算。

给定一个数组：

$$nums = [a₁, a₂, a₃, ..., aₙ]$$

我们定义它的 前缀和数组 prefix 为：(即前 i 个数的和)

$$prefix[i] = a₁ + a₂ + ... + aᵢ$$

并约定：prefix[0] = 0

这题是乘法，所以prefix[0] = 1;

#include <vector>
using std::vector;

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

    vector<int> prefix(n);
    vector<int> suffix(n);
    vector<int> result(n);
    prefix[0] = 1;

    for (i = 1; i < n; i++) {
      prefix[i] = nums[i - 1] * prefix[i - 1];
    }
    suffix[n - 1] = 1;

    for (i = n - 2; i >= 0; i--) {
      suffix[i] = nums[i + 1] * suffix[i + 1];
    }
    for (i = 0; i < n; i++) {
      result[i] = prefix[i] * suffix[i];
    }
    return result;
  }
};