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）找到排序数组的最小值和最大值之和。这是所需的总和，因为如果不是这两个，则至少有一对不能以相同的总和形成。希望我清楚。

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

Answer 1

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

Answer 2

找到数组的总和，将其加倍，然后除以N。