arrays - 判断数组中是否存在两个元素之和正好为X？

Question

给定一个包含 N 个元素的数组 A[] 和一个数字 x，检查 A[] 中的对与总和为 x 吗？

方法 1 = 给出 O(n lg n) 的排序。

方法 2 = 使用给出 O(n) 的哈希表。

我对方法 2 有疑问，如果使用链接，那么对于每个元素，我们必须在列表中搜索其补码，由于链接，在最坏的情况下可能会产生 O(n^2)。

我认为它只有在给定整数范围时才会起作用，这样我们就可以拥有哈希表而无需链式给出 O(n)。我说得对吗？

Answer 1

你可以试试下面的方法->

hash all elements in A[], like (key, value) = (A[i],true) 

for all elements in A[]:
    if hash(x-A[i])=true: it exists