Ответ 1
hash все элементы в A [перебираем массив и вставляем элементы в хэш-набор], затем итерации B и проверяем каждый элемент, если он находится в B или нет. вы можете получить среднее время выполнения O(|A|+|B|).
Вы не можете получить сублинейную сложность, поэтому это решение оптимально для анализа среднего случая, однако, поскольку хеширование не O(1) наихудшего случая, вы можете получить плохая производительность в худшем случае.
EDIT:
Если у вас недостаточно места для хранения хеш-набора элементов в B, вам может потребоваться определить вероятностное решение с помощью bloom filters. Проблема: могут быть некоторые ложные срабатывания [но никогда не ложные отрицательные]. Точность правильного увеличения увеличивается, поскольку вы выделяете больше места для фильтра цветения.
Другое решение, как вы сказали, sort, которое будет O(nlogn) time, а затем использовать двоичный поиск для всех элементов в B в отсортированном массиве.
Для 3-го этапа вы получаете такую же сложность: O(nlogn) с тем же решением, это займет примерно два раза, а затем на этапе 2, но все же O(nlogn)
EDIT2:
Обратите внимание, что вместо обычного хэша иногда вы можете использовать trie [зависит от типа ваших элементов], например: для ints, сохраните номер, поскольку это была строка, каждая цифра будет похожа на символ. с этим решением вы получаете решение O(|B|*num_digits+|A|*num_digits), где num_digits - количество цифр в ваших номерах [если они являются ints]. Предполагая, что num_digits ограничено конечным размером, вы получаете O(|A|+|B|) худший случай.