Given a magic number sum, to find if there are two numbers whose sum equals to the number

Two solutions:

O(n): Traverse the array, put (array[i],sum-array[i]) into the hashtable, then traverse again, if array[i] in the hashtable, it means there are two numbers in the array.

O(1): 每store一个数n，就用n和每个已经存在数据结构中的数字想加求和，将这个和作为key
插入hashtable中，比如首先是empty，依次存入以下数，相对应的hashtable的key：

insert 2 -> ht: empty,
insert 3 -> ht: 5 (2+3)
insert 10 -> ht: 5, 12(2+10), 13(3+10)
insert 1 -> ht: 5, 12, 13, 3, 4, 11
insert 7 -> ht: 5, 12, 13, 3, 4, 11, 9, 10, 17, 8
。。。

more space but faster

I have a question about second one.

The big O for O(1) is only the process of checking from the hashset, but for creating the hashset it still need O(n2).

Also I'm not sure how to print the pair of elements that added to sum from the second method.

yangwenzhou wrote:Two solutions:

O(n): Traverse the array, put (array[i],sum-array[i]) into the hashtable, then traverse again, if array[i] in the hashtable, it means there are two numbers in the array.

O(1): 每store一个数n，就用n和每个已经存在数据结构中的数字想加求和，将这个和作为key
插入hashtable中，比如首先是empty，依次存入以下数，相对应的hashtable的key：

insert 2 -> ht: empty,
insert 3 -> ht: 5 (2+3)
insert 10 -> ht: 5, 12(2+10), 13(3+10)
insert 1 -> ht: 5, 12, 13, 3, 4, 11
insert 7 -> ht: 5, 12, 13, 3, 4, 11, 9, 10, 17, 8
。。。

more space but faster