Оптимальный алгоритм нахождения слагаемых суммы? Есть две похожие задачи:Дан массив целых чисел (могут быть равны нулю, отрицательными и повторяться). Нужно найти в нём первую комбинацию из двух элементов, которая в сумме даст число N.
Пример:N = 10
[10, 5, 2, 3, 7, 5, -1]
^-----------^ 5 + 5 = 10
^--^ 3 + 7 = 10 <-- второй элемент встретился раньше,
чем в предыдущем случае,
поэтому берём эту паруДан массив простых чисел от M до N включительно. Нужно найти первую комбинацию из двух элементов, разница между которыми равна G.
Пример:G = 6
M = 100 N = 110
[101, 103, 107, 109] <-- простые числа от M до N
^---------^ 107 - 101 = 6 <-- пара появилась раньше
^---------^ 109 - 103 = 6
В обоих задачах, нужно учесть что:массив может иметь огромное кол-во элементов (более миллиона)подходящие комбинации элементов могут отсутствовать в массиве
У меня нет другой идеи кроме полного перебора, сравнивая сумму/разность всех элементов в такой последовательности:1 и 2, 1 и 3, 1 и 4, ...
2 и 3, 2 и 4, 2 и 5, ...
и т.д.
Но на огромном массиве этот метод становится непременим. Кроме того, если пары нет, я об этом узнаю только после полного прохода.
В первой задаче массив состоит из случайных значений, но во второй последовательность имеет более-менее равномерную распределённость и возрастает. Думаю, это как-то может помочь.
Какие более оптимальные методы поиска слагаемых можно применить для решения данных задач?

21 Авг 2019 в 06:07
148 +1
0
Ответы
1

Для решения обеих задач можно воспользоваться методом двух указателей (two pointers). Этот метод заключается в том, что два указателя двигаются по массиву в разных направлениях, пока не будет найдена требуемая комбинация.

Для первой задачи (нахождение пары чисел сумма которых равна N) можно использовать следующий алгоритм:

Отсортировать массив целых чисел.Установить два указателя: один в начале массива, другой в конце.Начать двигать указатели друг к другу, сравнивая сумму двух чисел с N.Если сумма равна N, вернуть эту пару чисел.Если сумма меньше N, увеличить левый указатель.Если сумма больше N, уменьшить правый указатель.Если указатели пересеклись и не найдена подходящая пара, вернуть сообщение о том, что такая пара отсутствует в массиве.

Для второй задачи (нахождение пары чисел с разностью равной G) алгоритм будет аналогичен, только вместо суммы проверять разность двух чисел.

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

20 Апр в 13:23
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Название заказа не должно быть пустым
Введите email
Бесплатные доработки
Гарантированные бесплатные доработки
Быстрое выполнение
Быстрое выполнение от 2 часов
Проверка работы
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Название заказа не должно быть пустым
Введите email
Доверьте свою работу экспертам
Разместите заказ
Наша система отправит ваш заказ на оценку 92 588 авторам
Первые отклики появятся уже в течение 10 минут
Прямой эфир