c - 在未排序的数组中找到差值为输入值 'k' 的一对数字

Question

如题所述，我想找到差为K的元素对

example k=4 and a[]={7 ,6 23,19,10,11,9,3,15}
output should be :
   7,11
   7,3
   6,10
   19,23
   15,19
   15,11

我已阅读 SO“find pair of numbers in array that add to given sum”中的先前帖子

为了找到一个高效的解决方案，需要多少时间？时间复杂度是O(nlogn)还是O(n)？ 我试图通过分而治之的技术来做到这一点，但我没有得到任何退出条件的线索......

如果一个有效的解决方案包括使用两个指针对输入数组进行排序和操作元素，那么我认为我应该采用最少的 O(nlogn)...

是否有任何与数学相关的技术可以在 O(n) 中带来解决方案。任何帮助表示赞赏..

Answer 1

您可以使用哈希表在 O(n) 中完成。将所有数字放入 O(n) 的哈希中，然后再次遍历所有数字以寻找 number[i]+k。哈希表在 O(1) 中返回"is"或“否”，你需要遍历所有数字，所以总数是 O(n)。任何具有 O(1) 设置和 O(1) 检查时间的集合结构都可以代替哈希表工作。