python - 如何在整数数组中找到所有有序的元素对，其总和位于给定的值范围内

Question

给定一个整数数组，找出数组中所有有序元素对的个数，其总和在给定范围 [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

我知道我的解决方案不是最优的执行此操作的更好算法是什么。

Answer 1

1. 对数组进行排序(比如按升序排列)。
2. 对于数组中的每个元素 x:
   • 考虑元素之后的数组切片。
   • 对这个数组切片进行二分查找 [a - x]，称之为 y0。如果未找到完全匹配项，则将比 [a - x] 更大的最接近匹配项视为 y0。
   • 输出从y0开始的所有元素(x,y)只要x + y <= b

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

O(nlogn) + O(k)

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

注意:如果您只需要计算对的数量，您可以在O(nlogn) 中完成。修改上述算法，使 [b - x](或下一个更小的元素)也被搜索。这样，您可以简单地根据第一个和最后一个匹配项的索引计算每个元素在 O(logn) 中的“匹配项”数。然后，这只是将它们相加以获得最终计数的问题。这样，初始的 O(nlogn) 排序步骤占主导地位。