Эту задачу можно решить двумя способами. Выбор определяется компромиссом между эффективностью использования времени, памяти или сложностью кода.
Простое решение
Очень простое и эффективное (по времени) решение — создание хэш-таблицы, отображающей целое число в целое число. Данный алгоритм работает, пошагово проходя весь массив. Для каждого элемента x в хэш-таблице ищется sum – x и, если запись существует, выводится (x, sum — x). После этого x добавляется в таблицу и проверяется следующий элемент.
Альтернативное решение
Давайте начнем с формулировки. Если мы попытаемся найти пару чисел, сумма которых равна z, то дополнение будет z – x (величина, которую нужно добавить к x, что бы получить z). Если мы попытаемся найти пару чисел, при суммировании которых получается 12, дополнением к -5 будет число 17.
Представьте, что у нас есть отсортированный массив {-2, -1, 0, 3, 5, 6, 7, 9, 13, 14}. Пусть first указывает на начало массива, а last — на его конец. Чтобы найти дополнение к first, мы двигаем last назад, пока не найдем искомую величину. Если first + last < sum, то дополнения к first не существует. Можно также перемещать first на встречу к last. Тогда мы остановимся, если first окажется больше, чем last.
Почему такое решение найдет все дополнения к first? Поскольку массив отсортирован, мы проверяем меньшие числа. Когда first + last меньше sum, нет смысла проверять меньшие значения, они не помогут найти дополнение.
Почему данное решение найдет все дополнения last? Потому что все пары формируются с помощью first и last. Мы нашли все дополнения first, а значит, нашли все дополнения last.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | void printPairSums (int[] array, int sum) { Arrays.sort(array); int first = 0; int last = array.length - 1; while (first < last) { int s = array[first] + array[last]; if (s == sum) { System.out.printIn(array[first] + "" + array[last]); first++; last--; } else { if (s < sum) first++; else last--; } } } |
Разбор по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT – Компанию»