题目链接 · 灵神原题解（署名来源）

$\mathit{\text{answer}}[i]$ 等于 $\mathit{\text{nums}}$ 中除了 $\mathit{\text{nums}}[i]$ 之外其余各元素的乘积。换句话说，如果知道了 $i$ 左边所有数的乘积，以及 $i$ 右边所有数的乘积，就可以算出 $\mathit{\text{answer}}[i]$。

于是：

• 定义 $\mathit{\text{pre}}[i]$ 表示从 $\mathit{\text{nums}}[0]$ 到 $\mathit{\text{nums}}[i-1]$ 的乘积。
• 定义 $\mathit{\text{suf}}[i]$ 表示从 $\mathit{\text{nums}}[i+1]$ 到 $\mathit{\text{nums}}[n-1]$ 的乘积。

我们可以先计算出从 $\mathit{\text{nums}}[0]$ 到 $\mathit{\text{nums}}[i-2]$ 的乘积 $\mathit{\text{pre}}[i-1]$，再乘上 $\mathit{\text{nums}}[i-1]$，就得到了 $\mathit{\text{pre}}[i]$，即

$$\mathit{\text{pre}}[i]=\mathit{\text{pre}}[i-1]\cdot \mathit{\text{nums}}[i-1]$$

同理有

$$\mathit{\text{suf}}[i]=\mathit{\text{suf}}[i+1]\cdot \mathit{\text{nums}}[i+1]$$

初始值：$\mathit{\text{pre}}[0]=\mathit{\text{suf}}[n-1]=1$。按照上文的定义，$\mathit{\text{pre}}[0]$ 和 $\mathit{\text{suf}}[n-1]$ 都是空子数组的元素乘积，我们规定这是 $1$，因为 $1$ 乘以任何数 $x$ 都等于 $x$，这样可以方便递推计算 $\mathit{\text{pre}}[1]$，$\mathit{\text{suf}}[n-2]$ 等。

算出 $\mathit{\text{pre}}$ 数组和 $\mathit{\text{suf}}$ 数组后，有

$$\mathit{\text{answer}}[i]=\mathit{\text{pre}}[i]\cdot \mathit{\text{suf}}[i]$$

优化前

Python 解法1

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]

        suf = [1] * n
        for i in range(n - 2, -1, -1):
            suf[i] = suf[i + 1] * nums[i + 1]

        return [p * s for p, s in zip(pre, suf)]

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n, 1);
        for (int i = 1; i < n; i++) {
            pre[i] = pre[i - 1] * nums[i - 1];
        }

        vector<int> suf(n, 1);
        for (int i = n - 2; i >= 0; i--) {
            suf[i] = suf[i + 1] * nums[i + 1];
        }

        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            ans[i] = pre[i] * suf[i];
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

优化：不使用额外空间

先计算 $\mathit{\text{suf}}$，然后一边计算 $\mathit{\text{pre}}$，一边把 $\mathit{\text{pre}}$ 直接乘到 $\mathit{\text{suf}}[i]$ 中。最后返回 $\mathit{\text{suf}}$。

题目说「输出数组不被视为额外空间」，所以该做法的空间复杂度为 $\mathcal{O}(1)$。此外，这种做法比上面少遍历了一次。

Python 解法3

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

        pre = 1
        for i, x in enumerate(nums):
            # 此时 pre 为 nums[0] 到 nums[i-1] 的乘积，直接乘到 suf[i] 中
            suf[i] *= pre
            pre *= x

        return suf

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> suf(n);
        suf[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            suf[i] = suf[i + 1] * nums[i + 1];
        }

        int pre = 1;
        for (int i = 0; i < n; i++) {
            // 此时 pre 为 nums[0] 到 nums[i-1] 的乘积，直接乘到 suf[i] 中
            suf[i] *= pre;
            pre *= nums[i];
        }

        return suf;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。返回值不计入。

更多相似题目，见下面动态规划题单中的「专题：前后缀分解」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 【本题相关】动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府