判断大小为N的ArrayList中两数和为N的Θ(n log n)算法疑问

首先直接回答你的问题：如果排序后用线性查找去寻找每个元素的补数（N - num），那总时间复杂度会变成Θ(n²)——排序的Θ(n log n)加上n次线性查找的Θ(n)，主导项会变成Θ(n²)，不符合要求。但只要换用合适的查找方式，就能把总复杂度维持在Θ(n log n)。

为什么线性查找会破坏复杂度？ #

排序本身是Θ(n log n)，但如果对每个元素都遍历整个数组找补数，这一步的时间是O(n) * n = O(n²)，而Θ(n²)的增长速度远快于Θ(n log n)，所以总复杂度就被拉到了Θ(n²)，达不到作业要求。

两种保持Θ(n log n)复杂度的方法 #

1. 排序 + 二分查找

因为数组已经排序了，我们可以用二分查找替代线性查找，每次查找的时间是Θ(log n)：

• 步骤：
  • 用归并排序或堆排序对ArrayList进行排序，耗时Θ(n log n)
  • 遍历数组中的每个元素num，计算需要找的补数target = N - num
  • 在排序后的数组中用二分查找寻找target，注意特殊情况：如果num == target，需要确保数组中至少有两个这样的元素（比如检查当前元素的下一个位置是否也是num，或者统计该元素的出现次数）
• 总复杂度：排序的Θ(n log n) + n次二分查找的Θ(n log n)，主导项还是Θ(n log n)，符合要求。

2. 排序 + 双指针法

这是更高效的一种方式，排序后只需要一次线性遍历（Θ(n)）就能完成检查：

• 步骤：
  • 先对数组进行排序，耗时Θ(n log n)
  • 初始化左指针left在数组起始位置（索引0），右指针right在数组末尾（索引n-1）
  • 循环直到left >= right：
    • 计算当前两指针元素的和sum = arr[left] + arr[right]
    • 如果sum == N，直接返回true（找到符合条件的两个数）
    • 如果sum < N，说明需要更大的数，把left右移一位
    • 如果sum > N，说明需要更小的数，把right左移一位
  • 循环结束后没找到，返回false
• 总复杂度：排序的Θ(n log n) + 线性遍历的Θ(n)，总复杂度还是Θ(n log n)，因为Θ(n log n)是主导项。

总结 #

只要避免使用线性查找，改用二分查找或双指针法，就能让整个算法的时间复杂度保持在Θ(n log n)。其中双指针法在实际运行中会更快一些，因为它只需要一次遍历，而二分查找需要n次查找操作。

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