决定给定数组中是否有两个整数a和b的程序=

Question

我需要编写一个程序来决定给定列表中是否有两个整数a和b，这样a + b = c。输入将是一个列表和整数c。在这种情况下，a == b，但是a必须在列表中出现两次。运行时必须在O(n*log(n))中。你知道吗

我曾尝试实现二进制搜索，但由于必须对列表进行排序，因此如果不对列表进行排序，则不会起作用，因为排序至少需要O(n*log(n))时间。我试图实现合并排序而不在最后合并，只得到a和b，但我不知道这是否是一个死胡同。你怎么开始呢？运行时不超过O(n*log(n))非常重要。你知道吗

Answer 1

就地排序可以在O(n log(n))时间内完成。随后的搜索也可以在O(n)时间内完成，结果总共是O(n log(n))。一旦数据被排序，对于数组的每个元素a，使用另一端的同时搜索来检查c - a是否也在数组中。这样你就可以遍历整个数组一次。这种方法是由@RockyLi提出的。它的优点是使用O(1)额外的内存：输入列表需要在适当的位置进行排序。你知道吗

如果使用O(n)额外的内存是可以接受的，那么您可以遵循@PatrickHaugh's suggestion。创建一个集合。将列表中的每个元素a添加到集合中。如果c - a已经在集合中，则返回True。这需要O(n)时间来完成（一次通过），并且不需要排序。但它很可能是你使用的内存量的两倍多。你知道吗

以下是玩具实现：

O（1）空间，O（n log（n））时间

def has_sum(lst, c):
    lst.sort()
    rev = reversed(lst)
    end = next(rev)
    for item in lst:
        while end > c - item:
            end = next(rev)
        if end == c - item:
            return True
        if item > end:
            return False

O（n）空间，O（n）时间

def has_sum(lst, c):
    found = set()
    for item in lst:
        if c - item in found:
            return True
        found.add(item)
    return False