как ускорить работу скрипта Задача на codewars, python

Question

Я новичёк, только начал изучение Python. Тут вроде все пересмотрел по моему запросу, не нашел. Точнее нашел, но на С++ :(

Сама задача не сложная по сути, найти пару чисел в списке образующих заданную сумму. (https://www.codewars.com/kata/54d81488b981293527000c8f/train/python) Подскажите какой иной путь решения этой задачи, я что-то в тупике уже сутки. Вроде как у меня алгоритм простой: Находим первую пару, внутри между ними ищем вторую пару, если нет то возвращаем первую.

Все предварительные тесты проходит, упираюсь в ограничение по времени работы. Сам код (добавлю ниже), изначально был проще, но суть та же. Похоже сам решение найти не смогу, открывать решение пока не хотелось бы, если можно мне бы просто указание на ошибку в логике или подсказку через что попробовать реализовать.

  def sum_pairs(ints, s):
    ind_first, ind_second, val_first, val_second = [], [], [], []
    search_index, x = 0, 0
    for number in ints:
        search_number = (s - number)
        search_index += 1
        search_list = ints[search_index:]
       # print('First for')
        if search_number in search_list:
            ind_first.append(ints.index(number))
            val_first.append(number)
            for x in range(search_index, len(ints)):
         #       print('second for')
                if ints[x] == search_number:
                    ind_second.append(x)
                    val_second.append(search_number)
                    if ind_first[0] < ind_first[-1]:
                        if ind_second[0] > ind_second[-1]:
                            return [val_first[-1], val_second[-1]]
                        return [val_first[0], val_second[0]]
                    else:
                        break
        else:
            continue
    if not val_first:
        return None
 #   return [val_first[0], val_second[0]]
print(sum_pairs([1, 4, 8, 7, 3, 15], 8) == [1, 7], "Basic: %s should return [1, 7] for sum = 8" )
print(sum_pairs([1, -2, 3, 0, -6, 1], -6) == [0, -6], "Negatives: %s should return [0, -6] for sum = -6" )
print(sum_pairs([20, -13, 40], -7) == None, "No Match: %s should return None for sum = -7" )
print(sum_pairs([1, 2, 3, 4, 1, 0], 2) == [1, 1], "First Match From Left: %s should return [1, 1] for sum = 2 " )
print(sum_pairs([10, 5, 2, 3, 7, 5], 10) == [3, 7], "First Match From Left REDUX!: %s should return [3, 7] for sum = 10 " )
print(sum_pairs([4, -2, 3, 3, 4], 8) == [4, 4], "Duplicates: %s should return [4, 4] for sum = 8" )
print(sum_pairs([0, 2, 0], 0) == [0, 0], "Zeroes: %s should return [0, 0] for sum = 0" )
print(sum_pairs([5, 9, 13, -3], 10) == [13, -3], "Subtraction: %s should return [13, -3] for sum = 10" )

Answer 1

Да вроде алгоритм проще некуда, первое, что пришло в голову...
Используем словарь для сохранения самого факта встретившихся значений. Временная сложность поиска в словаре - О(1).
Дальше просто идем по списку и проверяем (по словарю), было ли уже значение, которое необходимо добавить к текущему для получения требуемой суммы. Если было, выводим требуемую пару.
Общая временная сложность всего алгоритма - O(n).

def sum_pairs(ints, s):
    cache = {}
    for v in ints:
        if cache.get(s-v, False):
            return [s-v, v]
        cache[v] = True

БЛОГ НА HUSL

как ускорить работу скрипта Задача на codewars, python

Ответы (1 шт):