sumOfTwo Time Limit Exceeded CodeFights采访练习

Question

我正在尝试CodeFights.com上的sumOFTwo挑战,但我无法完成它以查看解决方案.我的所有测试都进行到第15次隐藏测试,并表示超过了时间限制.

挑战是 - 你有两个整数数组,a和b,以及一个整数目标值v.确定是否有一对数字,其中一个数字取自a,另一个数字来自b,可以加在一起得到v.如果存在这样的一对,则返回true,否则返回false.

我的代码是 -

def sumOfTwo(a,b,v):
    a.sort()
    b.sort()

    if(0 in a and v in b):
        return True
    elif(v in a and 0 in b):
        return True
    else:
        for i in a:
            for j in b:
                if(i + j == v):
                    return True
    return False

我知道它可以缩减到大约6行代码,但我不断添加行可以帮助代码更快地完成.我还缺少任何其他优化措施.

Answer 1

您可以将其中一个列表转到set,迭代另一个列表,看看是否v - value_from_list存在于set:

def sumOfTwo(a,b,v):
    b = set(b)

    return any(v - x in b for x in a)

print(sumOfTwo([3, 6, 7], [2, 1], 9))
print(sumOfTwo([3, 6, 7], [2, 1], 10))
print(sumOfTwo([3, 6, 7], [2, 1], 4))
print(sumOfTwo([3, 6, 7], [2, 1], 3))

输出:

True
False
True
False

O(n)中的时间复杂度.