前置知识点：Python实用技巧

在解决算法问题时，掌握一些Python高级工具能大幅提升效率：

collections.defaultdict(int)
用于自动初始化字典的默认值。当访问不存在的键时，会自动赋值为0，非常适合统计频率的场景：

from collections import defaultdict
count = defaultdict(int)
count['a'] += 1  # 无需判断键是否存在

float('inf')
表示数学上的无穷大，常用于初始化比较操作：

min_val = float('inf')
for num in [3,1,4]:
    min_val = min(min_val, num)  # 自动处理初始比较

问题分析：LeetCode 238

给定整数数组nums，要求返回新数组answer，其中answer[i]等于nums中除nums[i]外所有元素的乘积。限制条件：

• 不能使用除法运算
• 时间复杂度O(n)
• 空间复杂度O(1)（不计输出数组）

解法一：左右乘积数组

构建两个辅助数组：

• left[i]存储nums[i]左侧所有元素乘积
• right[i]存储nums[i]右侧所有元素乘积

def productExceptSelf(nums):
    n = len(nums)
    left, right = [1]*n, [1]*n
    
    for i in range(1, n):
        left[i] = left[i-1] * nums[i-1]
    
    for i in range(n-2, -1, -1):
        right[i] = right[i+1] * nums[i+1]
    
    return [left[i]*right[i] for i in range(n)]

解法二：空间优化版

利用输出数组动态存储中间结果，将空间复杂度优化到O(1)：

def productExceptSelf(nums):
    n = len(nums)
    res = [1] * n
    
    # 存储左侧乘积
    for i in range(1, n):
        res[i] = res[i-1] * nums[i-1]
    
    # 动态计算右侧乘积
    R = 1
    for i in range(n-1, -1, -1):
        res[i] *= R
        R *= nums[i]
    
    return res

复杂度分析

时间复杂度：
两种解法均为O(n)，需要两次线性遍历。

空间复杂度：
解法一需要O(n)额外空间，解法二优化到O(1)（输出数组不计）。

应用场景扩展

这种左右分解的思想还可应用于：

• 接雨水问题
• 股票买卖问题
• 任何需要前后缀信息的数组处理

掌握这种预处理技巧能有效解决许多数组相关的算法难题。