Поиск триплетов

Я знаю, что этот тип вопроса был опубликован раньше, но я хочу обсудить что-то новое. Так что я отправляю его.

Учитывая несортированный массив целых чисел, найдите все триплеты, которые удовлетворяют x ^ 2 + y ^ 2 = z ^ 2.

Например, если заданный массив равен - 1, 3, 7, 5, 4, 12, 13 Ответ должен быть - 5, 12, 13 и 3, 4, 5

Я предложил ниже алгоритм со сложностью O (n ^ 2) -

Сортировка массива в порядке убывания. - O (nlogn)
квадратный каждый элемент. - O (n)

Теперь он сводится к задаче нахождения всех триплетов (a, b, c) в отсортированном массиве так, что a = b + c.

Интервьюер настаивал на решении лучше, чем O (n ^ 2).

Я прочитал проблему 3SUM в Википедии, которая подчеркивает, что проблема может быть решена в O (n + ulogu), если числа находятся в диапазоне [-u, u], предполагая массив может быть представлен как бит-вектор. Но я не могу получить четкую картину дальнейших объяснений.

Может кто-то, пожалуйста, помогите мне понять, что происходит с хорошим примером?

Ответ 1

Прежде всего. Поиск всех триплетов в худшем случае - O(n^3). Предположим, что у вас есть номера n=3k. K из них 3, k равны 4 и k равны 5.

3,....,3,4,....,4,5,.....5

Есть такие k^3 = n^3/27 = O(n^3) триплеты. Просто распечатывая их, требуется время O(n^3).

Далее будет объяснение проблемы 3SUM в такой форме:

Есть числа s_1, ..., s_n, каждый из которых находится в диапазоне [-u;u]. Сколько триплетов a,b,c есть a+b=c?

трансформирующего. Получите 2 * u числа a_-u, ..., a_0, a_1, ... a_u. a_i - количество чисел s_j, что s_j = i. Это делается в O(n+u)
res = a_0 * sum(i=-u..u, i=/=0, C(a_i, 2)) + C(a_0,3) a_0 = 0
Постройте полином P(x) = sum(i = -u...u, a_i*x^(i+u).
Найдите Q(x) = P(x)*P(x) с помощью FFT.
Обратите внимание, что Q(x) = sum(i=-2u..2u, b_i*x^(i+2*u)), где b_i - количество пар s_u, s_k, что s_u+s_k = i (это включает в себя использование того же числа дважды).
Для всех четных i do b_i = b_i - a_(i/2). Это приведет к удалению с использованием того же номера дважды.
Сумма всех b_i*a_i/2 - добавьте это к res.

Пример:, чтобы быть более простым, я предполагаю, что диапазон чисел равен [0..u] и не будет использовать никаких + u по степеням x. Предположим, что мы имеем числа 1,2,3 - a_0 = 0, a_1 = 1, a_2 = 1, a_3 = 1

res = 0
P(x) = x + x^2 + x^3
Q(x) = x^2 +2x^3+3x^4+2x^5+x^6
После вычитания b_2 = 0, b_3 = 2, b_4 = 2, b_5 = 2, b_6 = 0
res += 0*1/2 + 2*1/2 + 2*0/2 + 2*0/2 + 6*0/2 = 1

Ответ 2

Другая возможность (кто может понять ум интервьюера?) - это переписать уравнение как:

 x^2 + y^2 = z^2
 x^2 = z^2 - y^2 = (z-y)(z+y)

Если бы мы знали простую факторизацию x ^ 2, мы могли бы просто перебрать все возможные факторизации в пару чисел p, q (с p < q) и вычислить

 x^2 = p.q = (z-y)(z+y)
 p+q = (z-y)+(z+y) = 2z
 q-p = (z+y)-(z-y) = 2y
 z = (p+q)/2
 y = (q-p)/2

Поэтому, учитывая факторизацию x ^ 2 = p.q, мы можем выработать значения z и y. Поместив все целочисленные значения в набор, мы можем проверить каждый возможный ответ за время O (1) (за проверку), посмотрев, находятся ли эти значения z, y в массиве (заботясь о том, чтобы отрицательные значения также были обнаружены).

Википедия говорит, что случайное выбранное целое имеет о log (n) -дивизорах, поэтому это должно принимать около n.log(n), предполагая, что вы можете сделать факторизацию достаточно быстро (например, если вы знали, что все целые числа были меньше миллиона, вы можете предварительно скопировать массив наименьшего коэффициента для каждого целого числа).