Имея 2 несортированных массива и сумму, задайте два числа, которые при сложении равны сумме

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

Я получил этот вопрос как вопрос об алгоритмах во время телефонного интервью, и это поставило меня в тупик. Интервьюер, похоже, полагал, что существует решение O(n).

Изменить: мой вопрос отличается от «возможных дубликатов», потому что этот вопрос включает в себя 2 массива, а не один.


person C. Parks    schedule 20.04.2017    source источник
comment
Возможный дубликат Найти пара элементов массива, сумма которых равна заданному числу   -  person shole    schedule 20.04.2017


Ответы (1)


Для несортированных массивов - заполните хеш-таблицу значениями первого массива и пройдитесь по второму, проверяя, существует ли Sum-B[i] в таблице.

person MBo    schedule 20.04.2017
comment
Спасибо! Думаю, мне нужно больше практики с вопросами, которые предполагают, что вы реализуете хеш-таблицу. - person C. Parks; 20.04.2017