найти триплет с заданной суммой

Question

Я уже давно борюсь с этими вопросами. Вопрос звучит так: -

У нас есть n ^ 2 числа. Нам нужно выяснить, существует ли триплет a, b, c такой, что a + b + c = 0. Для более общего случая a + b + c = k. (дается)

Существует решение со сложностью O (n ^ 2log (n)).

Любая помощь будет принята с благодарностью.

спасибо

Answer 1

Чтобы получить это в O (n²logn), вам нужно отсортировать числа. Найдите все комбинации из 2 чисел и выполните двоичный поиск, чтобы найти третье.

Верхняя граница намного выше для общей версии задачи.

Answer 2

Я написал грубое решение.

Это определенно можно сделать за O (n ^ 2). Вы не должны сортировать это.

Это расширение проблемы, которое требует суммирования двух чисел в х, а хитрость заключается в использовании хеш-таблицы.

def triplets(l, total):
    """Sum of 3 numbers to get to total 
    Basically an extension of the 2 table 
    """
    l = set( l)
    d = { }

    for i in l:
        remain = total - i

        inside = {}
        for j in l:
            if i == j:
                continue
            inside[j] = remain -j

        d[i] = inside

    good = set()

    for first, dic in d.iteritems():
        for second, third in dic.iteritems():
            if third in l:
                good.add( tuple(sorted([first, second, third])) )

    for each in good: 
        print each

triplets( [2, 3, 4, 5, 6], 3+4+5)

ПРИМЕЧАНИЕ: мы можем использовать метод быстрой сортировки для триплетов, который будет O (1).