Есть две похожие задачи:
- Дан массив целых чисел (могут быть равны нулю, отрицательными и повторяться). Нужно найти в нём первую комбинацию из двух элементов, которая в сумме даст число 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, ...
и т.д.
Но на огромном массиве этот метод становится непременим. Кроме того, если пары нет, я об этом узнаю только после полного прохода.
В первой задаче массив состоит из случайных значений, но во второй последовательность имеет более-менее равномерную распределённость и возрастает. Думаю, это как-то может помочь.
Какие более оптимальные методы поиска слагаемых можно применить для решения данных задач?
Средний
