Оптимизирующее решение Sum of Pairs: Codewars на Python

Мне нужна помощь в оптимизации кода для огромных списков с прибл. 10000000 элементов. Есть ли способ улучшить мой алгоритм или я должен попытаться создать новый, используя совершенно другой подход? Задача: учитывая список целых чисел и одно значение суммы, вернуть первые два значения (пожалуйста, проанализируйте слева) в порядке появления, которые в сумме образуют сумму.

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)

Вы можете использовать набор как lst1 вместо списка. Каждый раз, когда вы проверяете, находится ли n в lst1, это $ O (п) $ временная сложность. Вместо этого использование набора снизит это до $ O (1) $.