从两个列表中找到2个数字的最快方法,总和等于x

Question

我的代码:

n = 3
a1 = 0
b1 = 10
a2 = 2
b2 = 2

if b1>n:
    b1=n
if b2>n:
    b2=n

diap1 = [x for x in range(a1, b1+1)]
diap2 = [x for x in range(a2, b2+1)]

def pairs(d1, d2, n):
    res = 0
    same = 0
    sl1 = sorted(d1)
    sl2 = sorted(d2)
    for i in sl1:
        for j in sl2:
            if i+j==n and i!=j:
                res+=1
            elif i+j==n and i==j:
                same+=1
    return(res+same)

result = pairs(diap1, diap2, n)
print(result)

注意: n,a1,b1,a2,b2 可以改变.代码应该从2个列表中找到2个数字(每个1个),总和等于n.例如:对(a,b)和(b,a)不同,但(a,a)和(a,a)是同一对.因此,我的代码输出是正确的,对于上面的代码是1(1,2),但对于大输入,它需要太多时间.如何优化它以更快地工作？

Answer 1

使用 set() 进行快速查找...

setd2 = set(d2)

不要尝试所有可能的数字对。一旦你从第一个列表中确定了一个数字，比如说 i，只需看看 (ni) 是否在第二组中。

for i in sl1:
    if (n-i) in setd2:
        # found match
    else:
        # no match in setd2 for i