The fastest way to find 2 numbers from two lists that in sum equal to x

Question

My code:

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)

NOTE: n, a1, b1, a2, b2 can change. The code should find 2 numbers from 2 lists(1 from each) that in sum equal to n. For example: pairs (a, b) and (b, a) are different but (a, a) and (a, a) is the same pair. So, output of my code is correct and for the code above it's 1(1, 2) but for big inputs it takes too much time. How can I optimize it to work faster ?

Answer 1

Use set() for fast lookup...

setd2 = set(d2)

Don't try all possible number pairs. Once you fix on a number from the first list, say i, just see if (n-i) is in the second set.

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

Answer 2

The following way you can work the fastest and find the two numbers whose sum is equal to n and store them as well in a list of tuples.

s1 = set(list1)
s2 = set(list2)
nums = []
for item in s1:
    if n-item in s2:
       nums.append((item, n-item))