查找给定数组中是否存在一对 (a,b) 使得 a = b*2

Question

给定一个数组，如何找到其中是否有两个数字 (a, b) 使得 a = b*2

以最有效的方式。我用哈希表和 AVL 在 O(n*nlog(n)) 上解决了它，

但他们说在最坏的情况下可以在 O(nlog(n)) 中完成，在平均情况下可以在 O(n) 中完成。

例如：

arr = [1,3,12,2,6,7]

输出：真

解释：12 = 6*2

Answer 1

线性时间，线性空间解：

• 循环遍历数组中的所有元素。
• 这样做时保持一组。
• 如果当前值的一半存在于映射中或者当前值的双倍存在于映射中，则返回真，否则返回假。

伪代码：

set = []
for element in array: 
    if set.contains(element * 2) or (element % 2 == 0 and set.contains(element / 2)):
       return true
    set.add(element)
return false