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

  • , Задачки
  • 1 минута

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

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

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