algorithm - 查找数组中的数字对，所有对都给出相同的总和

Question

假设有一个大小为 N 的数组(N 总是偶数)。给定数组的所有元素形成一对，添加时给出相同的和。求和。这绝对不是作业。例如:

A = {1,4,3,2,5,6,8,7} 。 ans = 9 因为 { (1,8) , (2,7) , (3,6) , (4,5) } 形成和 9 的对。

也可以有重复项。B = {3,4,5,3,4,5}。回答 = 8

我试过的是

1) 对数组进行排序 = O(nlogn)。

2) 找到排序数组的最小值和最大值之和。这是所需的总和，因为如果不是这 2 个，则至少会有一对不能由相同的总和组成。希望我清楚。

现在我的问题是，这能否以某种方式在线性时间内完成？直接散列数字是不够的，因为事先不知道“总和”。

Answer 1

O(n) 时间遍历一组数字以找到最小值和最大值并将所有数字放入哈希表中。计算目标总和 t = max + min。然后让第二次 O(n) 次通过数字集；对于数字 x，计算 y = t-x，在哈希表中查找 y，如果找到，则报告该对。关于重复，您还可以在哈希表中保留数字计数。