如何从列表中高效找出和小于指定阈值的两数最大组合？

给定列表[2,5,14,18,44]，要找出和小于60的两数最大组合，正确结果是(14,44)。但目前用暴力枚举所有组合的方式实现，列表一长就跑得特别慢。

附上原代码：

import itertools

# build_list是存所有建筑及其造价的长列表
# build_power1是可用资金总额
# 先过滤掉造价超预算的建筑
build_list = [i for i in self.list_of_constructions if i['cost'] < build_power1]

# 生成所有两元素组合
iter_all_build_combos = itertools.combinations(build_list, 2)

list_all_build_combos_with_cost = []        
for combo in iter_all_build_combos:
    sum1 = combo[0]['cost'] + combo[1]['cost']
    list_all_build_combos_with_cost.append((sum1, combo))
# 排序后取最后一个就是最大和组合
list_all_build_combos_with_cost.sort()

暴力枚举所有组合的时间复杂度是O(n²)，列表越长越卡。换用双指针法能把时间压到O(n log n)（主要耗时在排序），步骤很清晰：

1. 先把过滤后的build_list按造价从小到大排序
2. 左指针放列表开头，右指针放末尾，初始化最大和max_sum和最优组合best_combo
3. 计算左右指针元素的造价和：
   • 如果和小于预算：这是有效组合，要是当前和比max_sum大，就更新max_sum和best_combo，然后左指针右移，试试更大的和
   • 如果和超预算：右指针左移，缩小总和
4. 遍历完就得到最优组合

对应代码：

# 过滤超预算建筑 + 按造价升序排序
build_list = sorted(
    [i for i in self.list_of_constructions if i['cost'] < build_power1],
    key=lambda x: x['cost']
)

max_sum = -1
best_combo = None

left, right = 0, len(build_list) - 1

while left < right:
    current_total = build_list[left]['cost'] + build_list[right]['cost']
    if current_total < build_power1:
        if current_total > max_sum:
            max_sum = current_total
            best_combo = (build_list[left], build_list[right])
        left += 1
    else:
        right -= 1

# best_combo就是要找的组合

效率提升原因 #

• 排序只需要O(n log n)，双指针遍历是O(n)，整体复杂度远低于暴力法的O(n²)
• 不用生成所有组合，内存占用也少很多，完全能处理超长列表

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