Найдите три индекса x, y, z таких, что M [x] + M [y] = N [z]

Question

Учитывая два массива (не отсортированные) M и N. Мне нужно найти три индекса x, y (в M) и z (в N), для которых M [x] + M [y] = N [z]. Мой первоначальный алгоритм принимает решение O (m * m * n). Обратите внимание: я должен найти индексы, и сортировка изменит индексы.

O (м * м * п) псевдокод (где т и п длина соответствующего массива):

for(int i = 0; i < m - 1; i++) 
    for(int j = i + 1; j < m; j++) 
     for(int k = 0; k < n; k++) 
      if(M[i] + M[j] == N[k] { 
       print i, j, k 
      } 

Я ищу более оптимальное решение.

Спасибо.

Answer 1

Вставьте M в массив хэшей (хеш-набор/хэш-таблица), поэтому у вас будет O(1) содержит чек. Затем перебрать все элементы в N и внутри этой петле перебрать ваш хэш-набор, псевдокод:

foreach(integer x in N) 
    foreach(integer setY in hashArray) 
     if (hashArray.Contains(x - setY)) 
     then your solution is: setY + (x-setY) = x; 

Вы можете найти эти вещи индексы в линейное время. Общее время работы: O(|N|*|M|). Имейте в виду, что вам может понадобиться обрабатывать угловые случаи (например, x = 2 * setY).