如何以低于O(n²)时间复杂度比较两数组元素并寻找和为2的跨数组数对？

嘿，我来帮你搞定这两个优化需求！咱们一步步拆解，把O(n²)的低效方案换成更优的实现：

一、低于O(n²)的数组元素比较 #

通常这类需求是要快速找出两个数组的共同元素，或者完成元素存在性验证。暴力枚举两两对比的O(n²)方案确实太慢，咱们用哈希集合来优化，时间复杂度能直接降到O(n + m)（n和m分别是两个数组的长度）。

思路 #

1. 优先把较短的数组转换成哈希集合（哈希表的元素查找时间是O(1)，选短数组能节省内存）；
2. 遍历另一个数组，逐个检查元素是否在这个集合里，就能快速筛选出共同元素（或完成存在性判断）。

代码示例（Python） #

def find_common_elements(arr1, arr2):
    # 选长度更小的数组转集合，压缩内存占用
    if len(arr1) > len(arr2):
        arr1, arr2 = arr2, arr1
    arr_set = set(arr1)
    common = []
    for num in arr2:
        if num in arr_set:
            common.append(num)
    # 按需去重，不需要去重的话直接返回common即可
    return list(set(common))

复杂度说明 #

• 时间：O(n + m)，转集合操作是O(n)，遍历检查是O(m)；
• 空间：O(min(n,m))，只存储较短数组的元素，内存使用更合理。

二、快速找出跨数组和为2的数对 #

暴力枚举所有数对的O(n*m)复杂度太拖沓，同样用哈希集合优化，时间能降到O(n + m)。

思路 #

1. 把其中一个数组的元素存入哈希集合；
2. 遍历第二个数组的每个元素num，计算需要匹配的目标值target = 2 - num；
3. 如果target存在于集合中，说明num（来自第二个数组）和target（来自第一个数组）的和为2，记录这个数对即可。

代码示例（Python） #

def find_sum_two_pairs(arr1, arr2):
    arr1_set = set(arr1)
    valid_pairs = []
    for num in arr2:
        target = 2 - num
        if target in arr1_set:
            # 可按需调整数对顺序，比如(target, num)表示arr1和arr2的元素
            valid_pairs.append((num, target))
    # 按需去重，不需要重复数对的话可以转集合再转列表
    return valid_pairs

额外优化 #

如果只需要找到任意一组符合条件的数对，不用遍历完整个数组，找到后直接返回即可：

def find_single_sum_two_pair(arr1, arr2):
    arr1_set = set(arr1)
    for num in arr2:
        target = 2 - num
        if target in arr1_set:
            return (num, target)
    return None  # 没有找到符合条件的数对

这样的实现在数组规模较大时，比暴力枚举的效率提升非常明显。

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