Вам даны массив и число N. Нужно вернуть True, если в массиве есть такие два числа A и B, что их сумма A + B даёт N. В противном случае нужно вернуть False.
Примеры:
[1, 2, 3, 4], 5 ⇒ True
[3, 4, 6], 6 ⇒ False
✔️Можно, конечно, применить брутфорс, но есть решение получше. Его сложность составит O(n). Вот как оно выглядит:
def two_sum(numbers, target):
index = {num: i for (i, num) in enumerate(numbers)}
n = len(numbers)
for i in range(n):
a = numbers[i]
b = target - a
if b in index:
j = index[b]
if i != j:
return True
return False
Здесь сначала создаётся словарь index, который хранит числа из массива в качестве ключей и их индексы в массиве в качестве значений. Затем идёт перебор элементов массива. Для каждого элемента a вычисляется число b, которое необходимо для достижения суммы target. Далее проверяется, содержится ли b в словаре index. Если да, то дополнительно проверяется, не совпадает ли индекс текущего элемента a с индексом элемента b. Если индексы различны, это означает, что была найдена пара чисел, сумма которых равна target.
#алгоритмы
#python