algorithm - 排序以找到目标对

Question

大家好，我在一本书中发现了这个有趣的排序应用:

Finding a target pair - How can we test whether there are two integers x, y members of set S such that x+y=z for some target z? Instead of testing all possible pairs, sort the numbers in increasing order and sweep. As S[i] increases with i, its possible partner j such that S[j]=z-S[i] decreases. Thus decreasing j appropriately as i increases gives a nice solution.

我花了很多时间试图弄清楚这个排序应用程序是如何工作的，但我做不到。你能帮忙吗？

Answer 1

想象一下这个集合:

[1, 2, 4, 6, 7, 8, 10, 13, 14, 17]

您必须在此集合中找到一对 x, y 的数字，使得 x+y = 17。

如果您的集合未排序，您可以检查每个可能的对，它很长(具有 O(n2) 复杂度)。

如果您的集合已排序，您可以从第一个和最后一个数字开始，如 x 和 y，然后通过递增 x< 在集合中移动 和递减 y:

1 + 17 --> Too big --> Decrease y
1 + 14 --> Too small --> Increase x
2 + 14 --> Too small --> Increase x
4 + 14 --> Too big --> Decrease y
4 + 13 = 17. STOP, you found a pair!

排序的复杂度为 O(nlogn)，查找对的复杂度为 O(n)。