Как улучшить алгоритм проверки наличия элемента в массиве, равного разнице между любыми двумя другими элементами в массиве?

Question

Я знаю, что это, по-видимому, простой вопрос.Но я не могу найти лучший подход, чтобы добиться большей эффективности.Вот что я пытаюсьЭто очень наивно, но я все еще не могу понять это правильно.

1. Сортировка массива.(Разделяй и властвуй)

2. a) Выбирайте один элемент за раз b) Перебирайте все оставшиеся элементы массива (в паре), чтобы получить разницу между ними, чтобы соответствоватьвыбранный элемент.

3. Повторяйте шаг 2, пока не будут найдены хотя бы все элементы.
4. Сохраните все элементы, соответствующие условию.
5. Печать сохраненных элементов.

Answer 1

Просто ради интереса, мы можем решить эту проблему за O(n log n + m log m) время, где m - диапазон, используя быстрое преобразование Фурье.

Сначала отсортируйте входные данные.Теперь рассмотрим, что каждое из достижимых расстояний между числами может быть достигнуто путем вычитания одной разностной суммы префикса из другой.Например:

input:            1 3 7
diff-prefix-sums:  2 6
difference between 7 and 3 is 6 - 2

Теперь давайте добавим итоговое значение (самую правую сумму префикса) к каждой стороне уравнения:

ps[r] - ps[l]       = D
ps[r] + (T - ps[l]) = D + T

Давайте перечислим различия:

1 3 7
 2 4

и префиксные суммы:

p     => 0 2 6
T - p => 6 4 0  // 6-0, 6-2, 6-6

Нам необходимо эффективно определить количество всех различных достижимых различий.Это похоже на умножение полинома с коэффициентами [1, 0, 0, 0, 1, 0, 1] на полином с коэффициентами [1, 0, 1, 0, 0, 0, 0] (нам не нужен нулевой коэффициент во втором наборе, поскольку он генерирует только степени, меньшие или равные T), чтомы можем выполнить за m log m время, где m - это степень, с помощью быстрого преобразования Фурье.

Результирующие коэффициенты будут:

  1 0 0 0 1 0 1
* 
  1 0 1 0 0 0 0
=> 
  x^6 + x^2 + 1
*
  x^6 + x^4

= x^12 + x^10 + x^8 + 2x^6 + x^4 

=> 1 0 1 0 1 0 1 0 1 0 0 0 0

Мы отбрасываем число градусов нижечем или равно T, и отобразите наши упорядоченные результаты:

1 * 12 = 1 * (T + 6) => 1 diffs of 6
1 * 10 = 1 * (T + 4) => 1 diffs of 4
1 *  8 = 1 * (T + 2) => 1 diffs of 2

Если какой-либо из коэффициентов, их отрицательных значений или T есть в нашем наборе элементов массива, у нас есть совпадение.

Answer 2

Условие A[i] - A[j] = A[k] равно A[i] = A[j] + A[k], поэтому мы можем искать сумму.

Сортировать массив.

Для каждого элемента поиска, если это сумма двух других, использующих подход с двумя указателями (увеличить нижний индекс, если сумма слишком мала, уменьшить верхний индекс, если сумма слишком большая)

Результирующая сложность квадратична