Optimizing solution of Sum of Pairs: Codewars in Python

Question

I need help to optimize my code for huge lists with approx. 10000000 elements. Is there a way to improve my algorithm or should I try to build a new one using a completely different approach? Task: given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that add up to form the sum.

def sum_pairs(ints, s):
    lst1 = []
    for n in ints:
        if n in lst1:
            return [s-n, n]
        lst1.append(s-n)

lst3 = list(range(1,10000000))

sum_pairs(lst3, 20000000)

*Times out :(

#Using set() every time we add new item to the list doesn't help

def sum_pairs(ints, s):
    lst1 = []
    for n in ints:
        lst2 = set(lst1)
        if n in lst2:
            return[s-n, n]
        lst1.append(s-n)

Answer 1

You could use a set as lst1 instead of a list. Every time you check if n is in lst1, it’s \$ O(n) \$ time complexity. Using a set instead will lower that to \$ O(1) \$.