面试经典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;
  }
};

leetcode hot 100 rewrite

#include <vector>
using std::vector;

class Solution {
    public:
        vector<int> productExceptSelf(vector<int> &nums)
        {
                int i, n = nums.size();
                vector<int> prefix_multiply(n);
                vector<int> suffix_multiply(n);
                vector<int> answer(n);

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

                suffix_multiply[n - 1] = 1;
                for (i = n - 2; i >= 0; i--) {
                        suffix_multiply[i] = suffix_multiply[i + 1] * nums[i + 1];
                }

                for (i = 0; i < n; i++) {
                        answer[i] = prefix_multiply[i] * suffix_multiply[i];
                }

                return answer;
        }
};