高效生成满足两数之和>阈值的数对：按和降序输出的最优算法问询

给定降序排列数组 a[1] > a[2] > ... > a[n] 与阈值 T，需找出所有满足 a[i]+a[j] > T 的数对 (i,j)（其中 i<j），分两种场景分析最优解法：

1. 无输出顺序要求：O(1)每对的字典序枚举算法 #

此场景下可直接按字典序（固定i从小到大，枚举j从i+1开始）输出符合条件的数对，算法伪代码如下：

1. i := 1;  
2. WHILE (i <= n-1) AND (a[i] + a[i+1] > T)
3.    j := i+1
4.    WHILE (j <= n) AND (a[i] + a[j] > T)
5.      Print(Found pair (i,j));
6.      j := j+1;
7.    ENDWHILE;
8.    i := i+1;
9. ENDWHILE

效率分析 #

• 外层循环的终止条件a[i]+a[i+1]>T是核心优化：因数组降序，若a[i]+a[i+1]<=T，则所有i'>=i的a[i']+a[i'+1]必然也<=T，无需继续遍历。
• 每个符合条件的数对仅被访问一次，总时间复杂度为O(k)（k为符合条件的数对数量），即每对输出平均耗时O(1)。

2. 数对需按两数之和从大到小输出：是否存在O(1)每对的解法？ #

目前主流最优解法是基于最大堆的多路归并思路，每输出一个数对需O(log n)时间，逻辑如下：

1. 初始将最大和的数对(1,2)入堆；
2. 每次弹出堆顶的最大和数对(i,j)并输出；
3. 若j+1<=n且(i,j+1)未入过堆，则将其入堆；
4. 若i+1<j且(i+1,j)未入过堆，则将其入堆；
5. 重复步骤2-4直到堆为空且无符合条件的数对。

关于O(1)每对解法的可行性分析 #

你提到的“若存在O(1)每对解法，T=0时可实现O(N)排序O(n²)个数”的推导逻辑成立，但针对两数和的特殊集合，目前不存在已知的O(1)每对解法，原因如下：

• 符合条件的数对的和序列并非单链单调结构，存在多个并行的候选最大值（例如a[1]+a[3]和a[2]+a[3]可能都是当前未输出的次大值）；
• 要准确跟踪并取出下一个最大和的数对，必须维护候选集合，最优方式是使用堆，每次弹出最大值的操作需O(log n)时间；
• 即使是T=0的极端场景（所有i<j的数对都需输出），由于两数和的降序序列无法通过简单指针遍历直接生成，仍无法避免O(log n)的每对操作开销。

结论 #

若严格要求按和从大到小输出，基于最大堆的O(log n)每对解法是当前已知的最优方案，暂时没有能达到O(1)每对的更高效算法。

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