java - 两个数之和等于给定数

Question

I have an array with positive integers in random order. A number x from the list is given ,we need to find any two numbers in the list having sum equal to x.Running time must be less than n^2.

{编辑} 我所做的是，我将所有小于 x 一半的数字放在一个数组中，将大于 x 一半的所有数字放在另一个数组中，所有大于 x 的数字都被丢弃然后我的想法是所需的两个数字必须来自两个数组(不是来自单个数组)并通过迭代我可以获得这两个数字。

现在对于最坏的情况，我有点困惑这种方法好吗？或者如果有人指导我比这更好的东西，我们也可以实现 log n 或 n *log n 吗？

Answer 1

您的解决方案是错误的，并且在 O(n^2) 中。

1. 这是错误的，因为考虑 x=5 和 arr=[1,2,3,5] - 所需的两个数字来自一个数组，不是来自两者。
   如果 arr=[3,3,6]，x=6，您会将两个 3 放在一个列表中(例如不大于 x/2)，将无法找到 3+3=6。
2. 您的算法在 O(n^2) 中运行，因为假设正好一半的元素大于 x¹，并且一半小于 x。然后，您必须检查的组合数是 (n/2*n/2)/2 = n^2/8

---

要在 O(nlogn) 中解决它，想一想如果给定一个数字 arr[i] 对数据进行排序会怎样，如果有现在排序的数组中的数字 x-arr[i]？

您甚至可以通过将元素放在哈希集中来将上述情况提高到 O(n) 平均情况，现在，给定一个数字 y，您可以如果 x-y 也在集合中，能否高效地找到？

编辑:
划掉的部分不再相关，因为 OP 编辑​​了问题，而是添加了新的关注原因。

---

(1) 比编辑问题中的 x/2。