面试 - 查找其和为已知的所有数组元素对 [英] Interview - find all pairs of array elements whose sum is known

问题描述

我被问这个问题：
给出一个 n 的数组 int code> int sum ，我需要返回所有对的数组的元素的和等于 sum

I was asked this question: given an array of size n of ints and int sum, I need to return all pairs of the array's elements whose sum is equal to sum

std::vector< std::pair<int,int> > find(int* arr,size_t n,int sum)

我使用散列表提出了一个O（n）时间解决方案：

The arrays is not sorted. I have proposed an O(n) time solution using a hash table:

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]

需要额外的空间为散列....什么大小应该选择的散列？哪个哈希函数？

The solution requires extra space for the hash.... What size should be chosen for the hash? Which hash function?

你觉得怎么样？有没有更好的方法来解决这个问题？

What do you think about that? Is there a better way to solve this?

我知道一个额外的解决方案存在：排序数组;基于当前和大于还是小于 sum

Upd。
这个问题不存在 - 我对正确实现哈希感兴趣。

Upd. It is not the same question for which answers exists - I am interested in the correct implementation of the hash.

推荐答案

可以使用unordered_set，它可以在O（1）中找到一个元素

you can use unordered_set which can find a element in O(1)

这篇关于面试 - 查找其和为已知的所有数组元素对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！