输入#

整数数组 nums

输出#

数组 answer，其中 answer[i] 等于除 nums[i] 外其余元素的乘积

约束条件#

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• 保证数组 nums 之中任意元素的全部前缀元素和后缀元素的乘积都在 32 位整数范围内

进阶约束#

你可以在 $O(1)$ 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

示例1#

1
输入：nums = [1,2,3,4]
2
输出：[24,12,8,6]

示例2#

1
输入：nums = [-1,1,0,-3,3]
2
输出：[0,0,9,0,0]

从暴力枚举出发#

最直接的做法：对于每个位置 i，遍历整个数组计算乘积，跳过自身：

1
class Solution:
2
    def productExceptSelf(self, nums: List[int]) -> List[int]:
3
        n = len(nums)
4
        ans = [1] * n
5

6
        for i in range(n):
7
            for j in range(n):
8
                if i != j:
9
                    ans[i] *= nums[j]
10

11
        return ans

瓶颈分析：时间复杂度 $O(n^2)$，当 $n \le 10^5$ 时，$10^{10}$ 次操作远超时间限制。而且内部循环做了大量重复计算——对于相邻的位置 i 和 i+1，它们共享了大量乘数，但暴力法每次都从头乘起。

优化方向：能否复用已经算过的乘积？如果我们提前算好每个位置的「左边所有数的乘积」和「右边所有数的乘积」，那么每个位置的结果就是两者相乘，只需 $O(1)$ 即可得到。

左右前缀积数组#

正如上文分析，我们可以用两个数组分别记录前缀积和后缀积：

• left[i]：nums[0] 到 nums[i-1] 的乘积（不含 nums[i]）
• right[i]：nums[i+1] 到 nums[n-1] 的乘积（不含 nums[i]）

那么 answer[i] = left[i] * right[i]。

1
class Solution:
2
    def productExceptSelf(self, nums: List[int]) -> List[int]:
3
        n = len(nums)
4
        left = [1] * n
5
        right = [1] * n
6
        ans = [1] * n
7

8
        # 从左到右计算前缀积
9
        for i in range(1, n):
10
            left[i] = left[i - 1] * nums[i - 1]
11

12
        # 从右到左计算后缀积
13
        for i in range(n - 2, -1, -1):
14
            right[i] = right[i + 1] * nums[i + 1]
15

16
        # 合并
17
        for i in range(n):
18
            ans[i] = left[i] * right[i]
19

20
        return ans

• 时间复杂度：$O(n)$，三次遍历
• 空间复杂度：$O(n)$，需要 left 和 right 两个额外数组

虽然时间已经最优，但题目进阶要求提出：能否只用 $O(1)$ 额外空间？

空间优化：用输出数组替代前缀数组#

观察上述代码，left 和 ans 计算时机可以合并——我们先用 ans 数组存储前缀积，然后在从右向左遍历时，用一个变量 r 跟踪后缀积，边乘边更新：

1
class Solution:
2
    def productExceptSelf(self, nums: List[int]) -> List[int]:
3
        n = len(nums)
4
        ans = [1] * n
5

6
        # 第一遍：ans[i] 存储 i 左边所有元素的乘积
7
        for i in range(1, n):
8
            ans[i] = ans[i - 1] * nums[i - 1]
9

10
        # 第二遍：从右向左，用 r 跟踪右边乘积，直接乘入 ans
11
        r = 1
12
        for i in range(n - 1, -1, -1):
13
            ans[i] *= r
14
            r *= nums[i]
15

16
        return ans

💡 关键优化：ans 数组一开始存放前缀积，然后从右向左遍历时「就地」乘上后缀积，一举两得。由于输出数组不计入额外空间，我们实现了 $O(1)$ 额外空间。

代码优化：双指针一次遍历#

上面的解法需要两次独立的遍历。有没有办法在一次遍历中同时完成前后缀积的累积？

答案是可以的。我们维护两个变量 l 和 r，分别记录从左到右和从右到左的累积乘积。在每次迭代中，l 代表当前位置 i 的「左边乘积」，r 代表对称位置 n-i-1 的「右边乘积」——两边同时推进，互不干扰：

1
class Solution:
2
    def productExceptSelf(self, nums: List[int]) -> List[int]:
3
        n = len(nums)
4
        l = r = 1
5
        res = [1] * n
6
        for i, x in enumerate(nums):
7
            res[i] *= l
8
            res[n - i - 1] *= r
9
            l *= x
10
            r *= nums[n - i - 1]
11
        return res

逐行解读这段代码的执行逻辑：

1. 初始化：l = r = 1，分别代表「从左到右」和「从右到左」的累积乘积。res 全为 1 作为初始值。
2. 循环体内：
   • res[i] *= l：将 i 位置乘上它左边所有元素的累积积
   • res[n - i - 1] *= r：将对称位置 n-i-1 乘上它右边所有元素的累积积
   • l *= x：把当前元素 x 纳入左边的累积
   • r *= nums[n - i - 1]：把对称位置的元素纳入右边的累积
3. 循环结束时，res[i] 恰好被乘上了「左边累积 × 右边累积」，即除自身之外的乘积。

🧠 直觉理解：想象你从数组两端同时出发。l 是你从左边一路捡起的元素的乘积，每到一个新位置，先把这个位置的结果乘上 l（这是「我左边的东西」），然后再把当前元素「装进」l 给后面的位置用。r 从右边做同样的事。两个方向在一次循环中交错推进，互不干扰，因为它们操作的是数组的两个不同位置。

复杂度#

• 时间复杂度：$O(n)$，只需一次遍历。
• 空间复杂度：$O(1)$（输出数组不计入额外空间），仅使用了 l、r 两个变量。

$O(n)$ 时间已是最优——因为输出结果需要为 $n$ 个位置分别计算，至少需要遍历一次数组。

三种写法的对比#

三种写法的时间复杂度均为 $O(n)$，差异在于常数因子和代码风格。面试中建议从「左右数组法」讲起，展示清晰的思维递进过程，最后落地到「两次遍历法」或「单次双指针法」。

💡 面试建议：面试官更看重你的思维过程而非最终代码。先说「我们需要前缀积和后缀积」，用左右数组法写出第一版，再逐步优化——这个过程本身就能展现你的问题分解和优化能力。

处理零值的情况#

nums 中可能包含 0（如示例2 [-1, 1, 0, -3, 3]），但上述算法天然能正确处理——因为前缀积会正常累积 0，后缀积同理。唯一需要注意的是：如果题目不保证乘积在 32 位范围内（本题保证了），可能需要考虑溢出问题。