Разработка алгоритма, обнаруживающего в массиве все пары целых чисел, сумма которых равна заданному значению.

Эту задачу можно решить двумя способами. Выбор определяется компромиссом между эффективностью использования времени, памяти или сложностью кода.

Простое решение

Очень простое и эффективное (по времени) решение — создание хэш-таблицы, отображающей целое число в целое число. Данный алгоритм работает, пошагово проходя весь массив. Для каждого элемента 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.

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 – Компанию»