Дан массив целых чисел ARRAY. Требуется определить, есть ли в этом массиве два числа, сумма которых равна заданному значению TARGET.
Задача очень популярна в алгоритмических секциях. Её часто можно встретить на собеседованиях по телефону в Facebook и Google. Я встречал её разновидность на onsite секции в Intercom.
Пример
ARRAY = [1, 7, 4, 2, -3]
TARGET = 9
Здесь элементы 7 и 2 в сумме дают искомое значение TARGET 9.
Решение в лоб
Мы можем перебрать все возможные пары чисел и проверить, равна ли их сумма заданному значению. Асимптотика алгоритмической сложности будет стремиться к O(n**2)
Решение за линейное время
Минус предыдущего решения – дорогой перебор пар значений. Чтобы избавиться от него, используем множество (set), в котором будем запоминать ранее встретившиеся значения. В цикле повторяем шаги:
- Если в множестве есть элемент, который в сумме с текущим элементом ARRAY даёт TARGET, завершаем цикл и возвращаем истинное значение
- Кладём текущий элемент из ARRAY в множество и переходим к следующему
Решение имеет линейную сложность O(n).
Вместо заключения
Подписывайтесь на канал, если хотите регулярно получать разборы задач с технических секций крупнейших IT-компаний. Регулярная практика развивает умение эффективно решать ежедневные рабочие задачи и конечно же поможет при поиске работы в современной IT-компании.