Учитывая вектор максимум 10 000 натуральных и отличных чисел, найдите 4 числа (a, b, c, d), таких что a + b + c = d

Question

Я решил эту проблему, следуя простому, но не оптимальному алгоритму. Я отсортировал вектор в порядке убывания и после этого вычитал числа от макс до мин, чтобы посмотреть, получу ли я + b + c = d. Обратите внимание, что я нигде не использовал тот факт, что элементы естественны, различимы и не более 10 000 элементов. Я полагаю, что эти детали являются ключом. У кого-нибудь здесь есть подсказка по оптимальному способу решения этой проблемы?

Заранее спасибо!

Позже Править: Моя идея звучит так:

'<<quicksort in descending order>>'

for i:=0 to count { // after sorting, loop through the array
    int d := v[i];
    for j:=i+1 to count {
        int dif1 := d - v[j];
        int a := v[j];

       for k:=j+1 to count {
           if (v[k] > dif1)
              continue;
           int dif2 := dif1 - v[k];
         b := v[k];

    for l:=k+1 to count {
 if (dif2 = v[l]) {
    c := dif2; 
     return {a, b, c, d}
 }
           }
        }
    }
}

Что вы думаете? (Извините за плохой отступ)

Answer 1

Раствор в O (n ² log n):

Вычисляет наборы всех возможных сумм и разниц:

{a _i + a _j : 1 <= i, j <= n} </p>

{a _i -a _j : 1 <= i, j <= n} </p>

(сохранить их в сбалансированном бинарном дереве поиска) и проверить, имеют ли они общий элемент. Если да, существуют i, j, k, l такие, что a _i + a _j = a _k - a _l , это _i + a _j + a _l = a _k .

Решение в O (a _n log a _n ), где a _n - наибольшее число в векторе:

Вычислить полином

(x ^{a ₁} + x ^{a ₂} + ... + x ^{a _n} ) ³

Вы можете сделать это в O (a _n log a _n ), используя Быстрое преобразование Фурье (сначала вычислите квадрат, затем третью степень; см. * 1069) * здесь для описания). Заметьте, что после умножения коэффициент x ^{b _i} был сформирован из умножения x ^{a _i} * x ^{a _j} * x ^{a _k} = x ^{a _i + a _j + a _k} для некоторых i, j, k. Проверьте, есть ли степень x ^{a _l} в полученном полиноме.

К сожалению, это позволяет использовать некоторые i, j, k дважды. Вычитание 3 (x ^{2a ₁} + ... + x ^{2a _n} ) * (x ^{a ₁} + ... + x ^{a _n} ) - 2 (x ^{3a ₁} + ... + x ^{3a _n} ) удалит эти x ^{a _i + a _j + a _k} .

Answer 2

Существует алгоритм Шамира и Шропеля, который решает эту проблему во времени O (N ^ 2) и с памятью O (N), когда N - количество входов. Это в основном то, что предлагает sdcvvc, но вместо того, чтобы хранить множества {a _i + a _j } как единое целое, он будет повторно вычислять только суммы в соответствующих интервалах. Это экономит память, но не увеличивает сложность времени.

Ричард Шрёппель, Ади Шамир: «Алгоритм A T = O (2 ^ (n / 2)), S = O (2 ^ (n / 4)) для некоторых NP-полных задач». SIAM J. Comput. 10 (3): 456-464 (1981)

Answer 3

Вот @ комментарий MicSim к ответу @ sdcvvc , реализованный в Python:

def abcd(nums):
    sums = dict((a+b, (a,b)) for a, b in combinations(nums, 2))

    for c, d in combinations(sorted(nums), 2): # c < d
        if (d-c) in sums:
            a, b = sums[d-c]
            assert (a+b+c) == d
            if a == c or b == c: continue # all a,b,c,d must be different
            a,b,c = sorted((a,b,c))
            assert a < b < c < d
            return a,b,c,d

Где combinations() может быть itertools.combinations() или

def combinations(arr, r):
    assert r == 2 # generate all unordered pairs
    for i, v in enumerate(arr):
        for j in xrange(i+1, len(arr)):
            yield v, arr[j]

Это O (N ² ) во времени и пространстве.

Пример:

>>> abcd(range(1, 10000))
(1, 2, 3, 6)