从 2 个列表中查找其总和等于给定值的对

Question

我们有两个整数数组a和b，以及一个整数目标值v。判断是否存在一对数字，其中一个数字取自a，另一个取自b，可以加在一起得到得到 v 的总和。Return 如果存在这样的对，则为真，否则 return 为假。

例如：对于 a = [1, 2, 3]、b = [10, 20, 30, 40] 和 v = 42，输出应为

sumOfTwo(a, b, v) = True

到目前为止我的代码：

def sumOfTwo(a, b, v):
    for x in a:
        for y  in b:
            if x+y == v:
                return True
    return False

我想减少执行时间，因为执行长列表需要很长时间。

Answer 1

如果先把b转成集合应该会快很多：

def sumOfTwo(a, b, v):
    b = set(b)
    return any(v - x in b for x in a)

对于蛮力解决方案，复杂度应该是 O(M + N) 而不是 O(MN)。

Find pair from 2 list whose sum is equal to given value