如何编写算法来检查数组/列表中任意两个数字的总和是否与给定数字相匹配？

Question

如何编写算法来检查数组/列表中任意两个数字的总和是否与给定数字的复杂度相匹配nlogn？

Answer 1

我确信有更好的方法,但这是一个想法:

这两项操作都是O(n log n).

Answer 2

这可以O(n)使用哈希表来完成.使用数组中的所有数字初始化表,数字作为键,频率作为值.遍历数组中的每个数字,并查看(sum - number)表中是否存在.如果有,你有一个匹配.在遍历数组中的所有数字后,您应该有一个所有对的列表,总计达到所需的数字.

array = initial array
table = hash(array)
S = sum

for each n in array
    if table[S-n] exists
        print "found numbers" n, S-n

n和table [Sn]两次引用相同数字的情况可以进行额外检查,但复杂性仍然存在O(n).

Answer 3

使用哈希表.将每个数字及其索引插入哈希表中.那么,让我们S成为你想要的总和.对于array[i]初始数组中的每个数字,请查看S - array[i]哈希表中是否存在索引不同的数字i.

平均情况是O(n),最坏的情况是O(n^2),如果您害怕最坏的情况,请使用二进制搜索解决方案.

是的,可能存在哈希冲突.例如,考虑包含`n`个的数组`{1,1,1,1,...,1,1,1,...}`.我们想要得到总和20.你会在哈希表中的相同位置添加所有的.然后,对于每个1,您将检查数组中是否有19.假设值19映射到哈希表中与值1相同的位置.这意味着对于每个`n`,你将在哈希表中进行`n`检查,为你提供二次时间复杂度.对于存在解决方案的情况可以找到类似的示例(使用3个值 - 一个占主导地位) (4认同)

Answer 4

让我们说我们想在阵列A中找到两个数字,当它们加在一起时等于N.

排序可以在O(n log n)中完成.搜索是在线性时间内完成的.