python - 如何使用循环找到给定值的一对搜索值？

Question

我正在尝试编写一个函数，该函数获取一个数字列表和一个整数，并返回一个元组，该元组包含列表中的一对数字，其总和必须最接近函数接收到的数字。
例如:最近的([10,22,28,29,30,40], 54) --> (22,30)
在循环中以 O(n) 的时间复杂度执行此操作对我来说很重要。
我的代码的问题是循环不想为我从列表开头取的任何值重新运行列表结尾......
我很感激帮助:)
感谢帮助者!

def closest(lst, x):
    max_num = 0
    cur = lst[0]
    final = 0
    my_tup = ()
    for num in lst[::-1]:
        max_num = cur + num
        if max_num <= x:
            if max_num > final:
                final = max_num
                my_tup = (cur, num)
            else:
                cur = lst[1]

    return my_tup

print(closest([10,22,28,29,30,40], 54))  ---> return: (22,29)

Answer 1

您可能没有注意到的重要部分是您的输入列表已排序。

10,22,28,29,30,40

这意味着您可以利用此信息在列表的单次扫描中找到您正在寻找的配对。直觉是，如果你需要更大的数字，你可以走到列表的末尾。这些解决方案被称为 two-pointer technique

您要解决的问题是 2SUM problem 的变体.网上有解决办法如 here

但是，我建议您通读前几个链接并尝试自己解决。