Оптимальный алгоритм нахождения слагаемых суммы?

Question

[artem78]

Есть две похожие задачи:

1. Дан массив целых чисел (могут быть равны нулю, отрицательными и повторяться). Нужно найти в нём первую комбинацию из двух элементов, которая в сумме даст число N.
   
   Пример:
   

   N = 10
   [10, 5, 2, 3, 7, 5, -1]
        ^-----------^      5 + 5 = 10
              ^--^         3 + 7 = 10  <-- второй элемент встретился раньше,
                                           чем в предыдущем случае,
                                           поэтому берём эту пару

   
   
   
2. Дан массив простых чисел от M до N включительно. Нужно найти первую комбинацию из двух элементов, разница между которыми равна G.
   
   Пример:
   

   G = 6
   M = 100  N = 110
   [101, 103, 107, 109]    <-- простые числа от M до N
     ^---------^           107 - 101 = 6  <-- пара появилась раньше
          ^---------^      109 - 103 = 6

   
   
   

В обоих задачах, нужно учесть что:

1. массив может иметь огромное кол-во элементов (более миллиона)
   
2. подходящие комбинации элементов могут отсутствовать в массиве
   

У меня нет другой идеи кроме полного перебора, сравнивая сумму/разность всех элементов в такой последовательности:

1 и 2, 1 и 3, 1 и 4, ...
2 и 3, 2 и 4, 2 и 5, ...
и т.д.

Но на огромном массиве этот метод становится непременим. Кроме того, если пары нет, я об этом узнаю только после полного прохода.

В первой задаче массив состоит из случайных значений, но во второй последовательность имеет более-менее равномерную распределённость и возрастает. Думаю, это как-то может помочь.

Какие более оптимальные методы поиска слагаемых можно применить для решения данных задач?

Answer 1

[tsarevfs]

Немного переформулируем задачу: найти первое такое число i, что найдется j от 0 до i-1, что a[i] + a[j] = N.

Comments

[tsarevfs]

Находить j можно быстрее чем перебором.

[tsarevfs]

Следующая подсказка:

spoiler

если мы знаем a[i], то нам нужно проверить встречалось ли a[j] == N - a[i] в предыдущих элементах. Есть структуры данных, которые умеют это делать за O(1)

[artem78]

tsarevfs: Можно ещё одну подсказку? :)

[tsarevfs]

artem78: В цикле перебираем потенциальные вторые элементы a[i].
поддерживаем set элементов встретившихся раньше. Если в сете есть N - a[i], то это подходящая пара.

spoiler

N = 10
a = [10, 5, 2, 3, 7, 5, -1]
def findFirstPair():
	visited = {}
	for i in range(len(a)):
		if N - a[i] in visited:
			print("First pair has indexes: (%d, %d) and values: (%d, %d)" % (visited[N - a[i]], i, N - a[i], a[i]))
			return
		visited[a[i]] = i
	return

findFirstPair()

[artem78]

tsarevfs: Большое спасибо! Я вряд ли придумал бы такое элегантное решение.

[artem78]

Можно задать ещё один вопрос? Вторую задачу решил так:

import math

def getPrimes(M, N):
  '''Решето Эратосфена'''
  N += 1
  sieve = set(range(2, N))
  for i in range(2, int(math.sqrt(N))):
    if i in sieve:
      sieve -= set(range(2*i, N, i))

  return sorted([i for i in sieve if i >= M]) #  <-- Как бы это оптимизировать?
  
def step(g, m, n):
    visited = set()
    for i, x in enumerate(getPrimes(m, n)):
        if x - g in visited:
            return [x - g, x]
        visited.add(x)

    return None

Но с большими числами/диапазонами этот код работает очень долго. Как можно его ускорить?

[Влад Григорьев]

artem78: первое чято бросается в глаза, это можно sorted([i for i in sieve if i >= M]), сделать так sorted(i for i in sieve if i >= M), так уже будет быстрее, второе зачем вам enumerate, если вы не где не использууете индекс в функции, уберите его и тоже пойдет быстрее.

[artem78]

Влад Григорьев: А в чём отличие sorted([i for i in sieve if i >= M]) от sorted(i for i in sieve if i >= M)?

[Влад Григорьев]

artem78: В том, что ты не создаешь объект list, а используешь генератор, что уменьшает использование памяти и объем вычислений

print(i for i in range(10))
print([i for i in range(10)])

<generator object <genexpr> at 0x7f97afe00fc0>
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Answer 2

[Матвей Правосудов]

Во втором примере даже алгоритма не нужно, раз числа идут подряд:

$g = 6;
$m = 100;
$n = 110;
$array = [100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110];

echo $array[0] . "-" . $array[$g - 1] . "=" . $g;

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

P. S. Только увидел, что там простые числа, хотя в примере у автора обычные числа.

Comments

[artem78]

Только увидел, что там простые числа, хотя в примере у автора обычные числа.

Пардон, сейчас исправлю.