O (NlogN) находит 3 числа, которые имеют сумму любого произвольного T в массиве

Question

Учитывая массив A целых чисел, найдите любые 3 из них, которые суммируют с любым данным T.

Я видел это в одном онлайн-сообщении, в котором утверждается, что у него есть решение O (NlogN).

Я знаю, что для 2 чисел хеш-таблица может помочь для O (N), но для 3 чисел я не могу найти ни одного.

Мне также кажется, что эта проблема звучит знакомо с некоторыми трудными проблемами, но я не могу вспомнить название и, следовательно, не могу найти ее в Google. (Хотя худшее, очевидно, O (N ^ 3), а с решением 2 чисел это действительно O (N ^ 2))

На самом деле это ничего не решает в реальном мире, просто доставляет мне неприятности ..

Есть идеи?

Answer 1

Я думаю, ваша проблема эквивалентна 3SUM.

Answer 2

Для задачи с тремя суммами вы не можете найти решение лучше, чем O (n ^ 2). Вы можете сослаться на http://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science

Answer 3

2SUM проблема может быть решена за время O (nlgn).

Сначала отсортируйте массив, который принимает не более O (nlgn) операций. Теперь на i-й итерации мы выбрали элемент a[i] и находим элемент -a[i] в оставшейся части массива (т. Е. От i+1 до n-1), и этот поиск можно проводить в двоичном поиске, который занимает максимум Время. Таким образом, в целом это займет O (nlgn) операций.

Но проблема 3SUM не может быть решена за O (nlgn) время. Мы могли бы уменьшить его до O (n ^ 2)

Answer 4

Поднято прямо с https://en.wikipedia.org/wiki/3SUM

    sort(S);

    for i=0 to n-3 do

        a = S[i];
        start = i+1;

        end = n-1;

        while (start < end) do

           b = S[start];
           c = S[end];
           if (a+b+c == 0) then
              output a, b, c;
              // Continue search for all triplet combinations summing to zero.
               start = start + 1
               end = end - 1

           else if (a+b+c > 0) then
              end = end - 1;
           else
              start = start + 1;
           end
        end
     end

Answer 5

Я думаю, что это всего лишь сумма подмножества проблема

Если это так, то NP-Complete.

РЕДАКТИРОВАТЬ: не имеет значения, это 3sum, как указано в другом ответе.

Answer 6

Звучит как домашнее задание ...

Если вы можете найти два значения, которые составляют N , но вы хотите расширить поиск до трех значений, не так ли, для каждого значения M в наборе посмотрите для двух значений, которые составляют (N - M) ? Если вы можете найти два значения, которые суммируются с определенным значением за время O (log N), то это будет O (N log N).