Однажды, на собеседовании в крупной российской IT компании, было предложено решить одну интересную задачу. Точный текст условия, к сожалению, привести нет возможности, однако суть задачи простая. 

Задача

Пусть дана последовательность целых чисел. Длина последовательности известна. Числа не отсортированы и могут повторяться. Необходимо найти в данной последовательности такие два числа M и N, чтобы их сумма была равна целому числу K ( M + N = K ). Будем считать, что K равно 5. Хотя можно выбрать любое другое целое число.

Для примера, возьмем последовательность (1):

7, -1, 1, -7, 0, -4, 3, 2, -5, -6, 8, -2  (1)

Тогда M = 3, а N = 2 ( 3 + 2 = 5 ), 
или   M = 7, а N = -2 ( 7 + (-2) = 5 )

Для решения задачи достаточно найти хотя бы одну подходящую пару чисел M и N. Ограничения по памяти не накладываются и главным критерием является асимптотическая сложность алгоритма. Решим эту задачу.

Программировать будем на C++. Хотя решение на другом языке не будет сильно отличаться. Для всех вариантов решения будем приводить описание алгоритма и пример кода.

Вариант 1, медленный: O(n^2)

Первое что приходит на ум и о чем лучше не говорить в слух - это метод полного перебора и сравнения каждого элемента с другими элементами последовательности. В этом случае действуем так: берем первый элемент и начинаем искать во всей входной последовательности такой элемент, чтобы в сумме с первым получилось 5 (число K). Если ничего не найдено, берем второй элемент и снова проходим всю последовательность, начиная с третьего элемента, в поисках подходящей пары. Как только пара будет найдена, алгоритм останавливается. Иначе продолжаем искать. 

Очевидно, что это очень неэффективный способ. Сложность алгоритма O(n^2). При большом объеме входных данных, поиск пары числе может занять довольно длительное время, особенно если нужной пары просто не существует (кстати, этой ситуации никто не исключал).

Не станем приводить реализацию данного алгоритма. Здесь все и так понятно. Попробуем решить задачу более эффективно. 

Вариант 2, с сортировкой: O(n*log(n))

Допустим, что мы отсортировали нашу последовательность. При этом сразу получаем сложность O(n*log(n)). Как теперь быстрее найти подходящую пару или сделать вывод, что такой пары не существует. Посмотрим внимательно на отсортированную последовательность (2):

-7, -6, -5, -4, -2, -1, 0, 1, 2, 3, 8  (2)

Тот факт, что элементы упорядочены, дает нам право "откидывать" из рассмотрения заведомо "неудовлетворительные" числа. Например, берем наименьшее число последовательности. Это -7. Пару для -7 может составить только число 12, так как 12 + (-7) = 5. Обращаясь к другому "краю" последовательности, мы понимаем, что 12 у нас в наличии нет и быть не может. Наибольшее число равно 8. Таким образом, число -7 можно "выкинуть" из дальнейшего рассмотрения, ведь пары для него у нас точно не будет. Переходим к числу -6 и повторяем сравнение с наибольшим числом последовательности. И так далее. Откинув лишнее слева, получим:

-2, -1, 0, 1, 2, 3, 8  (3)

Число -2 откидывать пока нельзя, так как подходящая пара - это число 7, которое может присутствовать в нашей отсортированной последовательности (непосредственно перед 8-кой). Раз "откидывать" числа слева больше нельзя, переходим к правому краю, и повторяем аналогичные шаги: берем 8, парой будет число -3. Но на данный момент наименьшее число последовательности равно -2. Значит 8 "откидываем". Число 3 отбросить пока нельзя, поэтому снова переходим к левому краю.

В итоге, в данном примере всё сведется к единственно возможной паре чисел, которые в сумме дают 5:

2, 3  (4)

Ответ может быть найден и раньше. Допустим, что в последовательности чисел присутствует 7. Тогда алгоритм остановится, когда последовательность будет вот в таком состоянии:

-2, -1, 0, 1, 2, 3, 7  (5)

Ответом будут крайние числа: M = 7, а N = -2

После сортировки достаточно всего лишь одного прохода, чтобы искомая пара чисел была найдена, а это значит что, сложность такого алгоритма целиком определяется сложностью задействованного алгоритма сортировки. То есть, раз сортировка имеет сложность O(n*log(n)), то и весь алгоритм будет иметь такую сложность.

Пример реализации описанного алгоритма на C++:

Стоит отметить, что, например, на языке Python этот алгоритм можно записать намного короче и понятнее. 

Итак, имеем сложность O(n*log(n)) - это хорошо! Однако отсутствие ограничений по памяти наталкивает нас на поиск еще более эффективного метода решения.

Вариант 3, быстрый: O(n)

Количество элементов нам известно, памятью нас не ограничивают. Такие условия позволяют нам задействовать для решения задачи очень эффективную структуру данных - хеш-таблицу. Важное свойство хеш-таблиц состоит в том, что, при некоторых разумных допущениях, поиск и вставка (и удаление) элементов в среднем выполняются за время O(1). Тогда наш алгоритм поиска двух чисел может быть таким:

  1. Берем очередной элемент из последовательности и вычисляем второе число, которое в сумме с текущим числом даст нам 5. 
  2. Ищем во вспомогательной хеш-таблице второе (рассчетное) число. Если такое число существует, то алгоритм останавливается, ответ найден. Иначе, добавляем рассматриваем элемент последовательности во вспомогательную хеш-таблицу. 
  3. Если в исходной последовательности еще есть нерассмотренные элементы, переходим к шагу 1. Иначе, алгоритм останавливается, ответа не существует.

Все очень просто! При этом не нужно отсортировывать последовательность. Главное, чтобы в процессе выполнения алгоритма часто не возникали коллизии и рехэш хеш-таблицы. Для этого мы можем изменить значение коэффициента заполнения хеш-таблицы (max_load_factor) и сразу указать сколько элементов будет храниться в хэш-таблице (reserve). Эти действия гарантируют нам сложность операций с хеш-таблицей равную O(1). А это значит, что весь алгоритм будет иметь сложность O(n). 

Приятно что, реализация алгоритма также упрощается:

Напоследок, докажем, что данную задачу невозможно решить еще эффективнее.

Вариант 4, еще быстрее: ???

Допустим дана последовательность неотсортированных целых чисел. Нужно найти два числа в последовательности, таких что их сумма была бы равна 5. Представим, что есть алгоритм, который решает эту задачу эффективнее, чем O(n). Следовательно, не все элементы последовательности участвуют в алгоритме.

Тогда допустим, что решения для данной последовательности нет, то есть нет такой пары чисел, которые в сумме были бы равны 5. Чтобы сделать такой вывод нужно проанализировать все числа последовательности, так как абсолютно любой элемент может участвовать в ответе. Следовательно, не может быть такого решения, которое всегда игнорировало бы какую-то часть элементов и имело сложность, например, O(log n).


На этом всё! Любые замечания и комментарии приветствуются!