如何在O(n+m)复杂度下从两个不同数组中找到相加等于指定值S的两个元素

你原有方案的问题在于列表的in查询时间复杂度为O(m)，导致整体时间复杂度达到O(n*m)。要达到要求的O(n+m)复杂度，核心是把查询操作的时间降到O(1)，可以借助哈希集合实现：

• 首先遍历第二个数组，把所有元素存入哈希集合，该过程时间复杂度为O(m)
• 再遍历第一个数组，对每个元素x，直接计算需要匹配的目标值S - x，在哈希集合中查询该目标值是否存在，平均查询时间为O(1)，该过程时间复杂度为O(n)
• 总时间复杂度为O(n + m)，完全符合题目要求，空间复杂度为O(m)

def finding_sum(arr1, arr2, s):
    # 构建第二个数组的哈希集合，时间O(m)
    arr2_set = set(arr2)
    # 遍历第一个数组，时间O(n)
    for x in arr1:
        y = s - x
        if y in arr2_set:
            return x, y
    # 没有符合条件的配对时返回空
    return None

• 如果你需要返回所有符合条件的配对，只需要把return逻辑改成把配对存入结果列表，遍历完所有元素后再返回即可，时间复杂度仍然保持O(n+m)
• Python的set底层是哈希表，平均插入、查询时间都是O(1)，算法题场景下默认按O(1)计算，符合时间复杂度要求
• 如果想要优化空间占用，可以选择长度更短的数组来构建哈希集合，只需要额外记录是否交换了两个数组，返回时调整x和y的顺序保证x来自第一个数组、y来自第二个数组即可，优化后空间复杂度为O(min(n,m))，时间复杂度不变。

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