Программа, которая решает, есть ли в данном массиве два целых числа a и b, так что a + b = c

Question

Мне нужно написать программу, которая решает, есть ли в данном списке два целых числа a и b, так что a + b = c.На входе будет список и целое число c.Возможно, в этом случае a == b, но a должно появиться в списке два раза.Время выполнения должно быть в O(n*log(n)).

Я пытался реализовать бинарный поиск, но так как список должен быть отсортирован для этого, он не будет работать, если список не отсортирован, потому что сортировказаймет не менее O(n*log(n)) времени.Я пытаюсь реализовать сортировку слиянием без слияния в конце и просто получаю a и b, но я не знаю, тупик ли это.Как бы вы могли начать?Очень важно, чтобы время выполнения не превышало O(n*log(n)).

Answer 1

Сортировка на месте может быть сделана за O(n log(n)) время.Последующий поиск также может быть выполнен за O(n) время, в результате чего в общей сложности O(n log(n)).После сортировки данных для каждого элемента a массива проверьте, есть ли в массиве также c - a, используя одновременный поиск с другого конца.Таким образом вы пройдете весь массив ровно один раз.Этот подход предлагается @ RockyLi .Он имеет преимущество использования O(1) дополнительной памяти: список входных данных должен быть отсортирован на месте.

Если используется O(n) допустима дополнительная память, вы можете следовать предложению @ PatrickHaugh .Создать набор.Добавьте каждый элемент, a, в списке к набору.Если c - a уже есть в наборе, вернуть True.Это требует O(n) времени для завершения (один проход) и не требует сортировки.Но это, вероятно, увеличит вдвое объем используемой памяти.

Вот игрушечные реализации:

O (1) пробел, O (n log (n)) время

def has_sum(lst, c):
    lst.sort()
    rev = reversed(lst)
    end = next(rev)
    for item in lst:
        while end > c - item:
            end = next(rev)
        if end == c - item:
            return True
        if item > end:
            return False

O (n) пробел, O (n) время

def has_sum(lst, c):
    found = set()
    for item in lst:
        if c - item in found:
            return True
        found.add(item)
    return False