如何实现O(n*log n)复杂度的数组两数和目标查找算法

你写的如下双层循环无法覆盖所有数对，不能保证找到符合要求的结果：

for (int i = 0; i < n; i++)
    for (int j = 1; j <= n; j = j*2)

这段代码的时间复杂度确实是O(nlogn)：内层j每次乘2，对于长度为n的数组，单轮内层循环只会执行log₂n次，总执行次数是n*log₂n，量级符合要求。但内层j的取值是跳跃的，只会取1、2、4、8…这类2的幂次下标，绝大多数下标位置都不会被访问到，会漏掉大量可能的数对组合，逻辑上是错误的。

以下两种方案都可以稳定在O(nlogn)复杂度，且不会遗漏任何可能的数对：

• 排序+双指针法
  1. 如果需要返回元素在原数组的下标，先拷贝原数组并记录每个元素的原始索引，之后对数组做升序排序，排序步骤时间复杂度为O(nlogn)
  2. 初始化左指针指向数组起始位（下标0），右指针指向数组末尾位（下标n-1）
  3. 循环计算两指针指向元素的和：
     • 和等于目标值：直接返回两个元素对应的结果
     • 和小于目标值：左指针右移，增大总和
     • 和大于目标值：右指针左移，减小总和
       双指针遍历全程仅需O(n)时间，整体复杂度保持O(nlogn)，只要存在符合要求的数对就一定能找到。
• 排序+二分查找法
  1. 同样先对带原始下标的数组做排序，复杂度O(nlogn)
  2. 外层遍历数组每个元素arr[i]，计算需要匹配的补值为target - arr[i]
  3. 对每个补值，在数组的剩余未遍历区间内用二分查找搜索是否存在对应值，单次二分查找的时间复杂度为O(logn)
     外层遍历n次，总复杂度为O(nlogn)，本质是对每个元素检查所有可能的匹配对象，不会漏过任何数对。

注意：不要为了凑O(nlogn)的复杂度量级刻意写跳跃步长的循环，复杂度是正确逻辑下的结果，不是靠刻意控制循环次数凑出来的。

内容的提问来源于stack exchange，提问作者Marko Rabrenovic