我被问到这个问题：给定一个大小n为ints 和的数组int sum，我需要返回数组元素的所有对，其总和等于sum
std::vector< std::pair<int,int> > find(int* arr,size_t n,int sum)
数组未排序。我提出了一个使用哈希表的 O(n) 时间解决方案：
traverse the arr
if arr[i] is in the hash
vector.push_back (make_pair(arr[i],sum-arr[i]));
else
insert to the hash sum - arr[i]
该解决方案需要额外的散列空间......应该为散列选择什么大小？哪个哈希函数？
你怎么看？有没有更好的方法来解决这个问题？
PS我知道存在一个额外的解决方案：对数组进行排序；根据当前总和是否大于或小于sum
更新。 存在哪些答案不是同一个问题——我对哈希的正确实现感兴趣。