algorithm - 排序以找到目标对

Question

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

寻找目标对 - 我们如何测试集合 S 中是否存在两个整数 x、y 成员，使得某个目标 z 的 x+y=z？不要测试所有可能的配对，而是按递增顺序对数字进行排序并扫描。当 S[i] 随 i 增加时，其可能的伙伴 j 使得 S[j]=zS[i] 减少。因此，随着 i 的增加，适当地减小 j 可以得到一个很好的解决方案。

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

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) 复杂度。