专访 - 找出所有对数组元素的总和是已知的 [英] Interview - find all pairs of array elements whose sum is known

问题描述

有人问我这样一个问题： 给定大小的数组 N INT s和 INT总和，我需要返回所有对数组元素的总和等于之

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?

P.S。 我知道一个额外的解决方案存在：对数组进行排序;从年底开始时两个指针遍历的基础如果目前的总和大于之

P.S. I know an additional solution exists: sort the array; traverse it with two pointers from the end and begining, based if current sum is greater or smaller than 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屋！