Найти пару / тройку, чья сумма меньше всего от заданного значения

Question

Есть 2 варианта этого вопроса.

1. Учитывая 2 массива целых, выберите один элемент из каждого массива, чтобы их сумма была наименьшей (численно) от заданного целого значения V. Sum может быть больше V.

2. Учитывая 3 массива целых чисел, выберите один элемент из каждого массива, чтобы их сумма была наименьшей (численно) от заданного целочисленного значения V. Сумма можетбыть больше V.

Я знаю, что для них есть наивное решение O (n ^ 2) и O (n ^ 3) соответственно, и я хотел бы спросить, есть липодход, который оптимизирует время работы.

Answer 1

Для первого случая вы можете отсортировать оба массива в O(nlogn), а затем для каждого элемента x в первом массиве найти V-x во втором массиве, используя алгоритм двоичного поиска / верхней границы.
Его общая сложность все равно будет O(nlogn), что меньше O(n*n).

Во втором случае вы можете применить аналогичный алгоритм со сложностью O(n*n*log(n)).