O (n) Алгоритм, чтобы определить, имеют ли 2 массива 2 элемента, которые в сумме дают число
Я изучаю на экзамен и наткнулся на этот вопрос, который кажется немного сложным.
Пусть A [1 ... n] и B [1 ... n] будут 2 массивами целых чисел, так что каждый элемент A или B находится в диапазоне от 0 до m, где m = O (n). (Полагаю, это означает, что m
Нам нужно разработать алгоритм O (n), который находит два элемента A [i] и B [j], такие что A [i] + B [j ] = заданное число k. Если их нет, выдается сообщение об ошибке.
Теперь об их сортировке не может быть и речи, так как лучшие алгоритмы сортировки - O (n lg n).
Можно использовать хеш-таблицу .. Или просто создать меньший массив X длиной m, чтобы каждый индекс считал вхождения числа в A .. затем мы переходим B .. вычисляем diff = k - B [j] .. и проверьте X [diff] .. если он больше нуля, то да, он существует, тогда мы могли бы пройти через A еще раз, чтобы найти его индекс ..
Что вы думаете, ребята