在未排序的数组中找到所有对 (x, y) 使得 x + y = z

Question

我有n个数字和一个数字z。我想创建一个算法（伪代码）来查找 O(nlogn) 中是否存在 x + y = z 对 (x,y)。

我认为我可以运行快速排序算法。然后我将有 2 个数组：array1（元素 < pivot）和 array2（元素 > pivot）。如果数组中的第一个元素 < z 那么我可以检查 array1 中的所有其他元素以找到 x+y=z 的对。否则，如果 array1 中的第一个元素是 >z，那么我将转到 array2 并执行相同的过程。我的建议是真的吗？

Answer 1

首先，对数组进行排序。
然后在排序后的数组的每一端设置一个pointer/index。
如果它们总和为 z，则保留它并将两个指针移向中间。
如果总和小于z，则将小端的指针向中间移动。
如果总和大于z，则将大端的指针向中间移动。
当指针meet/pass时，大功告成

Answer 2

您不需要对已经排序的序列进行排序，只需搜索它即可。

伪代码：

sort(sequence) // O(NlogN) sorts are well known
for element in sequence: // O(N) loop
    target = z - element // constant (assuming fixed size arithmetic)
    if target > min_element and target < max_element: // constant
        found = binary_search(target, sequence) // O(LogN) search

复杂度：O(NlogN (排序) + (N (循环) * LogN (搜索))) = O(NlogN)，根据需要

Answer 3

枢轴的想法行不通，因为没有好的枢轴候选者，而且检查未排序的半范围仍然是一项需要完成的 O(n) 任务n/2 次，整体复杂度为 O(n²).

您可以通过将所有元素添加到散列 table，然后检查每个元素 x 是否存在 z-x 元素来在 O(n) 中完成此操作而无需排序。 x=z/2 的情况是一种特殊情况，因为您需要验证输入数组中是否存在两个 z/2 值。

在未排序的数组中找到所有对 (x, y) 使得 x + y = z

Find all pairs (x, y) in an unsorted array so that x + y = z

sorting

algorithm

quicksort