28
правок
Изменения
Нет описания правки
Например : <tex> {A} = ({2,3,1,0,-4,-1}) </tex>. Решением данной задачи является, например, четверка чисел <tex> 3 + 1 + 0 - 4 = 0</tex> или <tex> 0 + 0 + 0 + 0 = 0</tex>.
Наивный алгоритм заключается в переборе всевозможных комбинаций чисел. Это решение работает за <tex> {O(N^4)}</tex>. Теперь, с помощью '''Meet-in-the-middle''' мы можем сократить время работы до <tex> {O((N + N)\log{N}}) = {O(N^2\log{N}}) </tex>.
Для этого заметим, что сумму <tex> a + b + c + d = 0 </tex> можно записать как <tex> a + b = -(c + d)</tex>. Мы будем хранить все <tex> {N^2} </tex> пар сумм <tex> a + b </tex> в массиве <tex> sum </tex>, который мы отсортируем. Далее перебираем все <tex> {N^2} </tex> пар сумм <tex> c + d </tex> и проверяем [[Целочисленный двоичный поиск|бинарным поиском]], есть ли сумма <tex> -(c + d) </tex> в массиве <tex> sum </tex>.
