面试算法题：数组元素排除自身乘积求解（O(n)、无除法）

哈哈，这道题我之前面试也碰到过，当时一开始也没想到绕开除法的O(n)解法，后来琢磨明白核心是用左右乘积遍历的思路，完美贴合题目两个约束，下面给你一步步拆解：

核心思路 #

我们不需要计算整个数组的总乘积再除以当前元素（毕竟不能用除法），而是分别计算每个元素左侧所有元素的乘积，以及右侧所有元素的乘积，最后把这两个乘积相乘，就是当前元素对应的结果。而且我们可以不用额外创建两个辅助数组，直接在结果数组上操作，把空间复杂度降到O(1)（结果数组不算额外空间，因为题目要求返回新数组）。

具体步骤 #

1. 初始化结果数组：先创建一个和原数组长度相同的结果数组res，初始值全为1。
2. 正向遍历计算左侧乘积：维护一个变量left_prod，初始为1。遍历原数组时，把当前left_prod赋值给res[i]（这就是当前元素左侧所有元素的乘积），然后更新left_prod为left_prod * nums[i]，为下一个元素的左侧乘积做准备。
   比如原数组[3,1,2,4]，遍历后res会变成[1,3,3,6]：
   • 第一个元素左侧无元素，所以res[0] = 1；
   • 第二个元素左侧是3，res[1] = 3；
   • 第三个元素左侧是3*1=3，res[2] =3；
   • 第四个元素左侧是312=6，res[3]=6。
3. 反向遍历计算右侧乘积并合并结果：维护一个变量right_prod，初始为1。从数组末尾开始倒着遍历，把res[i]乘以right_prod（这样就得到了左侧乘右侧的结果），然后更新right_prod为right_prod * nums[i]，为前一个元素的右侧乘积做准备。
   继续用上面的例子：
   • 第四个元素右侧无元素，res[3] =6*1=6，然后right_prod变成1*4=4；
   • 第三个元素，res[2]=3*4=12，right_prod变成4*2=8；
   • 第二个元素，res[1]=3*8=24，right_prod变成8*1=8；
   • 第一个元素，res[0]=1*8=8；
     最终res就是[8,24,12,6]，完全符合要求。

代码实现（Python） #

def product_except_self(nums):
    n = len(nums)
    res = [1] * n
    
    # 正向遍历填左侧乘积
    left_prod = 1
    for i in range(n):
        res[i] = left_prod
        left_prod *= nums[i]
    
    # 反向遍历填右侧乘积并合并
    right_prod = 1
    for i in range(n-1, -1, -1):
        res[i] *= right_prod
        right_prod *= nums[i]
    
    return res

# 测试示例
test_nums = [3,1,2,4]
print(product_except_self(test_nums))  # 输出: [8,24,12,6]

为什么这个解法符合要求？ #

• 时间复杂度O(n)：只做了两次线性遍历，没有嵌套循环，完全满足O(n)的要求；
• 无除法操作：全程用乘法计算左右乘积，完美规避除法的限制，同时也不会出现数组含0时的除法错误问题；
• 空间优化：除了必须返回的结果数组，只用到了两个变量，空间复杂度是O(1)，非常高效。

内容的提问来源于stack exchange，提问作者Almas Abdrazak