algorithm - 查找具有给定差异的对

Question

给定 n、k 和 n 个整数。你如何找到差为 k 的整数对？

有一个n*log n 解决方案，但我想不通。

Answer 1

你可以这样做:

• 对数组进行排序
• 对于每个项目 data[i]，确定其两个目标对，即 data[i]+k 和 data[i]-k
• 对这两个目标的排序数组进行二分查找；如果找到，将 data[i] 和 data[targetPos] 添加到输出。

排序在 O(n*log n) 中完成。 n 搜索步骤中的每一步都需要 2 * log n 时间来寻找目标，总时间为 O(n*log n)