除了自身以外数组的乘积

阅读要点

• 题目要求计算每个元素除自身外所有元素的乘积，且不能使用除法。
• 使用前缀积数组记录每个元素左侧所有数的乘积。
• 从右向左遍历，用一个变量 R 记录右侧乘积，并同步更新结果数组。
• 最终空间复杂度为 O(1)（输出数组不计入额外空间）。

题目

238. 除了自身以外数组的乘积 - 力扣（LeetCode）

解法

题目要求求出每一个元素两边数的总乘积。例如，对于数组 [1,2,3,4]，输出应为 [24,12,8,6]。

最容易想到的方法是：对于每个元素，分别计算其左侧所有数的乘积和右侧所有数的乘积，然后相乘。这可以通过前缀积数组和后缀积数组来实现。前缀积数组 pre 中 pre[i] 存储 nums[0] 到 nums[i-1] 的乘积，后缀积数组 suf 中 suf[i] 存储 nums[i+1] 到 nums[n-1] 的乘积，则结果 res[i] = pre[i] * suf[i]。

但题目要求空间复杂度为 O(1)（输出数组不计入额外空间）。因此我们可以只保留前缀积数组，后缀积用一个变量 R 动态维护。具体做法是：先计算前缀积数组 pre，然后从右向左遍历，用一个变量 R 记录当前元素右侧所有数的乘积，并同步更新 pre[i] 为 pre[i] * R，同时更新 R 为 R * nums[i] 供下一个元素使用。

答案

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre = [1] * n
        # 计算前缀积：pre[i] = nums[0] * ... * nums[i-1]
        for i in range(1, n):
            pre[i] = pre[i-1] * nums[i-1]
        
        R = 1  # 后缀积，初始为1（最右侧元素右侧无元素）
        # 从右向左遍历，更新结果
        for i in range(n-1, -1, -1):
            pre[i] *= R
            R *= nums[i]
        return pre

代码解释：

• 第一遍循环计算前缀积，pre[0] 保持为 1，因为第一个元素左侧没有元素。
• 第二遍循环从右向左，R 初始为 1。对于 i = n-1，pre[n-1] 乘以 R=1 不变，然后 R 更新为 nums[n-1]。对于 i = n-2，pre[n-2] 乘以 R（此时 R 为 nums[n-1]），得到左侧乘积乘以右侧乘积，然后 R 更新为 nums[n-2] * nums[n-1]，以此类推。

收获

• 本题的关键在于将空间复杂度从 O(n) 优化到 O(1)，同时保持时间复杂度 O(n)。
• 使用变量代替数组是常见的空间优化技巧。
• 注意边界条件：第一个元素左侧乘积为 1，最后一个元素右侧乘积为 1。

扩展思考：如果题目允许使用除法，可以先将所有数相乘，然后每个结果除以自身。但本题明确禁止除法，且当数组中有 0 时除法会失效。因此前缀积/后缀积方法是更通用的解法。