1 подписчик

2SUM: Задача с собеседования в Facebook

1 сентября 20191 сен 2019

1 мин

Дан массив целых чисел ARRAY. Требуется определить, есть ли в этом массиве два числа, сумма которых равна заданному значению TARGET. Задача очень популярна в алгоритмических секциях. Её часто можно встретить на собеседованиях по телефону в Facebook и Google. Я встречал её разновидность на onsite секции в Intercom. Пример ARRAY = [1, 7, 4, 2, -3]

TARGET = 9

Здесь элементы 7 и 2 в сумме дают искомое значение TARGET 9. Решение в лоб Мы можем перебрать все возможные пары чисел и проверить, равна ли их сумма заданному значению. Асимптотика алгоритмической сложности будет стремиться к O(n**2) Решение за линейное время Минус предыдущего решения – дорогой перебор пар значений. Чтобы избавиться от него, используем множество (set), в котором будем запоминать ранее встретившиеся значения. В цикле повторяем шаги: Решение имеет линейную сложность O(n). Вместо заключения Подписывайтесь на канал, если хотите регулярно получать разборы задач с технических секций крупнейших IT-компаний. Регулярная п

TARGET = 9

Оглавление

Пример
Решение в лоб
Решение за линейное время

Дан массив целых чисел 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-компании.