python - 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)。