是否存在优于O(N²)复杂度的Python解法？预算购机问题优化

你的原解法用双重循环枚举所有键盘和驱动器的组合，时间复杂度为O(N*M)（N是键盘数量，M是驱动器数量），当列表规模较大时效率会显著下降。确实存在更优的解法，核心思路是排序+双指针，时间复杂度可降至O(N log N + M log M)，排序的时间是流程主导，远优于暴力枚举的O(N*M)。

优化解法思路 #

1. 对键盘列表做升序排序，对驱动器列表做降序排序（也可以反过来，只要保证一个从低价到高价遍历，另一个从高价到低价遍历）；
2. 初始化两个指针：k_ptr 从键盘列表起始位置（最便宜的键盘）开始，d_ptr 从驱动器列表起始位置（最贵的驱动器）开始；
3. 遍历过程中计算当前组合的总花费：
   • 若总花费 ≤ 预算：记录该花费，然后将k_ptr右移一位（尝试更贵的键盘，争取得到更大的合法花费）；
   • 若总花费 > 预算：将d_ptr右移一位（尝试更便宜的驱动器，让总花费符合预算）；
4. 遍历结束后，若存在合法花费则返回最大值，否则返回-1。

代码实现 #

def get_money_spent(keyboards, drives, budget):
    # 升序排序键盘，降序排序驱动器
    keyboards_sorted = sorted(keyboards)
    drives_sorted = sorted(drives, reverse=True)
    
    max_spent = -1
    k_ptr = 0
    d_ptr = 0
    
    len_k = len(keyboards_sorted)
    len_d = len(drives_sorted)
    
    # 快速判断是否存在合法组合：最便宜的键盘+最便宜的驱动器是否超预算
    if keyboards_sorted[0] + drives_sorted[-1] > budget:
        return -1
    
    while k_ptr < len_k and d_ptr < len_d:
        current_total = keyboards_sorted[k_ptr] + drives_sorted[d_ptr]
        if current_total <= budget:
            # 更新最大花费
            if current_total > max_spent:
                max_spent = current_total
            # 尝试更贵的键盘
            k_ptr += 1
        else:
            # 当前组合超预算，尝试更便宜的驱动器
            d_ptr += 1
        # 提前终止：找到刚好等于预算的组合
        if max_spent == budget:
            return max_spent
    
    return max_spent

效率对比 #

暴力解法的时间复杂度是O(NM)，当N和M都是10000时，需要执行1亿次循环；而优化后的排序仅需约1000014≈14万次操作，双指针遍历仅需2万次，效率提升非常明显。

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