如何优化Python中求解数组三数最大和的三层嵌套for循环代码

原代码使用三层嵌套循环实现，时间复杂度为O(n³)，仅适合极小长度的数组，且存在全负数场景结果错误、未校验数组长度的潜在问题，可按以下思路优化：

核心逻辑说明 #

你的需求是选出3个下标互不重复的元素求最大和，本质就是取数组中数值最大的3个不同下标的元素之和，无需遍历所有三元组组合。

优化方案1：排序法（实现最简，时间复杂度O(n log n)） #

直接对数组元素绑定下标后倒序排序，取前3个元素即可：

arr = [1000,2000,6000,7000,3000,4000,5000,8000]
def fun(num):
    # 先校验数组长度合法
    if len(num) < 3:
        raise ValueError("数组长度不能小于3")
    # 绑定元素和原下标，按元素值倒序排序
    sorted_with_idx = sorted(enumerate(num), key=lambda x: x[1], reverse=True)
    top3 = sorted_with_idx[:3]
    pairs = tuple(item[1] for item in top3)
    max_sum = sum(pairs)
    print(pairs)
    print(max_sum)

fun(arr)

优化方案2：单次遍历法（效率最高，时间复杂度O(n)） #

遍历一次数组，维护当前最大的三个值，适合处理超长数组场景：

arr = [1000,2000,6000,7000,3000,4000,5000,8000]
def fun(num):
    if len(num) < 3:
        raise ValueError("数组长度不能小于3")
    # 初始化三个变量存前三大的数，初始值设为负无穷适配全负数场景
    first = second = third = float('-inf')
    for n in num:
        if n > first:
            third = second
            second = first
            first = n
        elif n > second:
            third = second
            second = n
        elif n > third:
            third = n
    pairs = (first, second, third)
    max_sum = sum(pairs)
    print(pairs)
    print(max_sum)

fun(arr)

边界优化说明 #

• 修复了原代码max_num初始为0，当数组全为负数时结果错误的问题
• 增加了数组长度校验，避免数组长度小于3时报未定义变量pairs的错误
• 两种优化方案相比原三层循环，性能提升幅度随数组长度增长指数级上升，当数组长度为1000时，原方案需要执行近10亿次循环，优化方案仅需最多1000次运算

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