Для двух массивов a и b. Найдите все пары элементов (a1, b1), которым принадлежит a1 к массиву A и b1 принадлежит массиву B, сумма которого a1 + b1 = k

Я ищу решение следующего алгоритма с минимальной сложностью времени и пространства.

Для двух массивов a и b найдите все пары элементов (a1, b1) такой, что a1 принадлежит массиву A, а b1 принадлежит массиву B, сумма которого a1 + b1 = k (любое целое число).

Я смог придумать подход O (n log n), в котором мы отсортируем одно из в массиве указано A, и для каждого элемента b в массиве B выполните двоичный поиск в отсортированном массиве A для значения (Kb).

Можем ли мы его еще улучшить?