如何查找总和位于给定值范围内的整数数组中的所有有序元素对

给定一个整数数组，查找数组中总和位于给定范围 [a,b] 内的所有有序元素对的数量

这是一个 O(n^2) 的解决方案

'''
counts all pairs in array such that the 
sum of pair lies in the range a and b
'''
def countpairs(array, a, b):
    num_of_pairs = 0
    for i in range(len(array)):
        for j in range(i+1,len(array)):
            total = array[i] + array[j]
            if total >= a and total <= b:
                num_of_pairs += 1
    return num_of_pairs

我知道我的解决方案不是最佳的 有什么更好的算法可以做到这一点。

1. 对数组进行排序（例如按升序排列）。
2. For each element x in the array:
   • 考虑数组切片after元素。
   • 在此数组切片上执行二分查找 [a - x]，将其称为 y0。如果没有找到完全匹配，则考虑最接近的匹配bigger比 [a - x] 为 y0。
   • 输出从 y0 开始的所有元素 (x, y)，只要 x + y

时间复杂度当然对输出敏感，但这仍然优于现有算法：

O(nlogn) + O(k)

其中 k 是满足条件的对的数量。

注意：如果您只需要count对的数量，你可以这样做O(nlogn)。修改上述算法，以便也搜索 [b - x]（或下一个较小的元素）。这样，您可以计算每个元素的“匹配”数量O(logn)只需从第一场和最后一场比赛的索引即可。然后只需将它们相加即可得出最终计数。这样，初始O(nlogn)排序步骤占主导地位。