判断给定数组中是否有两个整数 a 和 b 使得 a + b = c 的程序

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 是否也在数组中。您将以这种方式恰好遍历整个数组一次。建议采用这种方法。它具有使用 O(1) 额外内存的优点：输入列表需要就地排序。

如果使用O(n)额外的内存可以接受，可以按照。创建一个集合。将列表中的每个元素 a 添加到集合中。如果 c - a 已经在集合中，则 return True。这需要 O(n) 时间来完成（一次通过），并且不需要排序。但它可能会使您使用的内存量增加一倍以上。

以下是玩具实现：

O(1) space, 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)space,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

判断给定数组中是否有两个整数 a 和 b 使得 a + b = c 的程序

Program which decides if there are two integers a and b in a given array such that a + b = c

python

arrays

mergesort