求两数组元素差值小于x0的高效计算方案（当前O(n²)）

嘿，这个问题我之前做算法题的时候碰到过，暴力遍历O(n²)的方法在n稍微大一点（比如超过1000）的时候就会明显卡壳，给你分享两个时间复杂度降到O(n log n)的更优方案，亲测好用：

方法一：排序 + 双指针法 #

这是效率最高的方案之一，核心是利用排序后的数组特性，让指针单向移动，避免重复计算：

1. 预处理排序：先把数组A和B分别按升序排序，排序的时间复杂度是O(n log n)，这是整个流程的时间瓶颈；
2. 双指针遍历：初始化两个指针i（指向A的起始位置）和j（指向B的起始位置）；
3. 配对满足条件的元素：
   • 对于每个A[i]，移动j指针直到B[j] > A[i] - x0（推导：A[i] - B[j] < x0 等价于 B[j] > A[i] - x0）；
   • 由于A和B都是升序的，j只需要单向移动（不需要回退），所以这一步整体是O(n)时间；
   • 此时B中从j到末尾的所有元素，都和A[i]满足差值小于x0，直接记录这些元素对即可；
4. 移动i指针，重复上述步骤直到遍历完A。

示例验证 #

拿你给出的例子：A=[1,2,3]、B=[2,3,4]、x0=2

• 排序后A、B不变；
• i=0（A[i]=1）：A[i]-x0=-1，B中所有元素都大于-1，所以j停在0，记录(1,2),(1,3),(1,4)；
• i=1（A[i]=2）：A[i]-x0=0，B中所有元素都大于0，j仍在0，记录(2,2),(2,3),(2,4)；
• i=2（A[i]=3）：A[i]-x0=1，B中所有元素都大于1，j仍在0，记录(3,2),(3,3),(3,4)；
  最终得到所有符合条件的元素对。

方法二：排序 + 二分查找法 #

如果觉得双指针的逻辑有点绕，二分查找的实现会更直观，利用排序数组的二分特性快速定位边界：

1. 预处理排序：把数组B按升序排序（A可以不排序，不影响结果）；
2. 遍历+二分定位：
   • 对于A中的每个元素num，计算阈值：threshold = num - x0；
   • 在排序后的B中，用二分查找找到第一个大于threshold的元素的位置pos；
   • B中从pos到末尾的所有元素，都和num满足差值小于x0，记录这些元素对；
3. 遍历完A后得到最终结果。

代码示例（Python） #

import bisect

# 输入示例
A = [1, 2, 3]
B = [2, 3, 4]
x0 = 2

# 先排序B
B_sorted = sorted(B)
result = []

for num in A:
    threshold = num - x0
    # 用bisect_right找到第一个大于threshold的元素索引
    pos = bisect.bisect_right(B_sorted, threshold)
    # 生成所有符合条件的元素对
    for b_num in B_sorted[pos:]:
        result.append((num, b_num))

print(result)

运行结果：

[(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)]

复杂度对比 #

• 暴力法：O(n²)，n=1e4时需要1e8次运算，极易超时；
• 上述两种方法：整体时间复杂度O(n log n)，n=1e4时仅需约1.4e5次运算，性能提升非常明显。

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