Редактировать: Нижеприведенный ответ относится к версии этой проблемы, в которой вам нужен только один триплет, который складывается таким образом. Если вы хотите их всех, так как потенциально возможно хотя бы O (n^2) возможных выходов (как указано ex0du5) и даже O (n^3) в патологических случаях повторных элементов, вы не собираетесь бить простой алгоритм O (n^2), основанный на хешировании (сопоставление от значения к списку индексов с этим значением).
Это по существу the 3SUM problem. Без потенциально неограниченно больших элементов наиболее известные алгоритмы составляют приблизительно O(n^2), но мы только доказали, что для большинства моделей вычислений оно не может быть быстрее, чем O(n lg n).
Если целочисленные элементы находятся в диапазоне [u, v], вы можете сделать несколько другую его версию в O(n + (v-u) lg (v-u)) с помощью FFT. Я собираюсь описать процесс преобразования этой проблемы в эту проблему, решить ее там, а затем выяснить ответ на вашу проблему, основанный на этом преобразовании.
Проблема, которую я знаю, как решить с помощью БПФ, чтобы найти арифметическую последовательность длиной 3 в массиве: то есть, последовательность a, b, c с c - b = b - a, или что то же самое, a + c = 2b.
К сожалению, последний шаг преобразования назад не так быстр, как хотелось бы, но я расскажу об этом, когда мы доберемся туда.
Назовём исходный массив X, который содержит целые числа x_1, ..., x_n. Мы хотим найти индексы i, j, k таких, что x_i + x_j = x_k.
Найти минимальное и максимальное uv из X в O(n) времени.Пусть u' будет min(u, u*2) и v' be max(v, v*2).
Построить двоичный массив (bitstring) Z длины v' - u' + 1; Z[i] будет иметь значение, если X или его номер [x_1*2, ..., x_n*2] содержит u' + i. Это значение O(n) для инициализации; просто пройдите по каждому элементу X и установите два соответствующих элемента: Z.
Поскольку мы строим этот массив, мы можем сохранить индексы любых дубликатов, которые мы находим во вспомогательном списке Y. Как только Z будет завершен, мы просто проверяем на 2 * x_i за каждые x_i в Y. Если таковые имеются, мы закончили; в противном случае дубликаты не имеют значения, и мы можем забыть о Y. (Единственная ситуация немного сложнее, если 0 повторяется, то нам нужно три различных его копии, чтобы получить решение.)
Теперь решение вашей проблемы, т.е. x_i + x_j = x_k, появится в Z как три evenly- а некоторые простые алгебраические манипуляции дают нам 2*x_j - x_k = x_k - 2*x_i. Обратите внимание, что элементы на концах являются нашими специальными удвоенными записями (от 2X), а один из них является регулярным (от X).
Рассмотрим Z как представление полинома p, где коэффициент для члена степени i является Z[i]. Если X - [1, 2, 3, 5], то Z - 1111110001 (потому что у нас есть 1, 2, 3, 4, 5, 6 и 10); p затем 1 + х + х + х + х + х + х.
Теперь, помните из средней школы алгебры, коэффициент х гр в произведении двух многочленов равна сумма по всем а, Ь с а + Ь = с коэффициента первых полиномиального по для x a раз второй коэффициент для x b. Таким образом, если мы рассмотрим д = р, коэффициент х 2j (для J с Z[j] = 1) будет сумма по всем я из Z[i] * Z[2*j - i]. Но так как Z является двоичным, это точно количество триплетов i, j, k, которые равномерно распределены в Z. Обратите внимание, что (j, j, j) всегда является таким триплетом, поэтому мы заботимся только о единицах со значениями> 1.
Затем мы можем использовать Fast Fourier Transform найти P 2 в O(|Z| log |Z|) времени, где |Z| является v' - u' + 1. Мы выберем другой массив коэффициентов; назовите его W.
Петля на каждом x_k в X. (Напомним, что наши желаемые равномерно распределенные элементы центрированы по элементу X, а не 2*X.) Если соответствующий W для этого дважды, то есть W[2*(x_k - u')], равен 1, мы знаем, что это не центр каких-либо нетривиальных прогрессий, и мы можем пропусти это. (Как утверждалось ранее, это должно быть только положительное целое.)
В противном случае это может быть центр прогрессии, который мы хотим (поэтому нам нужно найти i и j). Но, к сожалению, это может быть также центр прогрессии, который не имеет нашей желаемой формы. Поэтому нам нужно проверить. Переверните остальные элементы x_i из X и проверьте, есть ли тройка с 2*x_i, x_k, 2*x_j для некоторых j (путем проверки Z[2*(x_k - x_j) - u']). Если это так, у нас есть ответ; если мы пройдем через все X без хита, тогда FFT найдет только ложные ответы, и мы должны проверить другой элемент W.
Таким образом, последний шаг - это O (n * 1 + (число x_k с W [2 * (x_k - u ')]> 1, которые на самом деле не являются решениями)), возможно, O(n^2), что очевидно, не в порядке. Должен быть способ избежать генерации этих ложных ответов на выходе W; если бы мы знали, что у любого подходящего коэффициента W определенно был ответ, этот последний шаг будет O(n), и все будет хорошо.
Я думаю, что для этого можно использовать несколько иной полином, но я не получил его на самом деле. Я подумаю об этом еще немного ....
частично на основе this answer.
Набор не является массивом. Этот ответ неверен. Например, рассмотрим массив, в котором элементы _all_ равны нулю. Затем все пары элементов массива равны каждому отдельному элементу. Просто перечислить каждую пару для суммы O (n^2). Свяжите хэш-таблицу с контейнерами совпадающих элементов, и вы получите амортизацию O (n^2) для вычисления структуры данных, которая представляет все возможные тройки (или O (n^3) для печати в виде троек). – ex0du5
@ ex0du5 здесь есть простая эквивалентность. Вы можете идентифицировать дублированные числа в одном проходе O (n), а затем обрабатывать эти суммы за время O (n). Если вы еще не нашли их, разделите их, и теперь вы уменьшите проблему до заданной проблемы, описанной выше. И наоборот, заданная задача разрешима, если у нас есть решение проблемы массива.Таким образом, они в основном одинаковы, хотя и различны в деталях. – btilly
Спасибо, что указали, что вне @ ex0du5; Я добавил обработчик дубликатов (как было предложено btilly) к алгоритму. – Dougal