Как решить проблему парных сумм в python с временной сложностью O (nlogn) или O (n)?

Question

сумма пар в массиве Дан случайный целочисленный массив A и число x. Найдите и распечатайте пару элементов в массиве, сумма которых равна x. Массив A может содержать повторяющиеся элементы. При печати пары сначала напечатайте меньший элемент. То есть, если допустимой парой является (6, 5), выведите «5 6». Не существует ограничений, что из 5 пар, которые должны быть напечатаны в 1-й строке. Вы можете печатать пары в любом порядке, просто следите за порядком элементов в паре.

Формат ввода: Строка 1: целое число N (размер массива) Строка 2: элементы массива (разделенные пробелом) Строка 3: целое число х

Выходной формат: Строка 1: пара 1 элементов (разделенных пробелом) Строка 2: пара 2 элементов (разделенных пробелом) Строка 3: и так далее

Ограничения: 1 <= N <= 1000 1 <= x <= 100 </p>

Пример ввода:

9
1 3 6 2 5 4 3 2 4
7

Пример вывода:

(1 6)
(3 4)
(3 4)
(2 5)
(2 5)
(3 4)
(3 4)

Мой подход :: 1. Взять 2 указателя / маркера начала и конца указывая на первый и последний элемент массива соответственно: 2. отсортировать массив -o (nlogn) 3. пока начало <конец проверить сумму с помощью указателей начала и конца Если сумма по указателям больше, чем фактическая сумма, уменьшите указатель конца с конца до 1 и, если он меньше, увеличьте указатель начала до начала + 1. </p>

код:

def pairSum(arr, x):
    arr.sort()  # nlogn
    i = 0
    j = len(arr) - 1

    while i < j:
        if arr[i] + arr[j] > x:
            j -= 1

        elif arr[i] + arr[j] < x:
            i += 1

        else:  # got the match  arr[i] +arr[j] ==x
            if arr[i] <= arr[j]:
                print(arr[i], arr[j])

                if arr[j - 1] == arr[j]:
                    j -= 1

                elif arr[i + 1] == arr[i]:
                    i += 1
                else:
                   i += 1
                   j -= 1

            else:
                print(arr[j], arr[i])
                if arr[i + 1] == arr[i]:
                    i += 1
                elif arr[j - 1] == arr[j]:
                    j -= 1
                else:
                    i += 1
                    j -= 1

Я пробовал эту проблему, и она отлично работает для уникального элемента, но не работает для дублирующих элементов, и это потому, что, пока l oop, он завершается рано. Пожалуйста, поделитесь своими мыслями:)

Answer 1

Для сложности O (n) вы можете использовать словарь, чтобы собрать числа, которые соответствуют совпадающей сумме (то есть target-n), и получить к ней прямой доступ по мере продвижения по списку:

numbers = [1, 3, 6, 2, 5, 4, 3, 2, 4]
target  = 7

matches = dict()
for n in numbers:
    for m in matches.get(n,[]):
        print(f"{n} {m}" if n<m else f"{m} {n}")
    matches.setdefault(target-n,[]).append(n)

выходные данные:

1 6
2 5
3 4
3 4
2 5
3 4
3 4

обратите внимание, что, когда в списке есть дубликаты, на самом деле невозможно полностью достичь O (n), потому что число результатов для печати может быть экспоненциально> n

Answer 2

Первый: если вы отсортировали массив и получили while i < j:, это означает, что в первом else: условие if arr[i] <= arr[j]: всегда выполняется, поэтому я бы просто упростил его.

Второй: ваш проблема в том, когда у вас есть arr[i + 1] == arr[i] и arr[j - 1] == arr[j]. В вашей реализации в этом случае вы уменьшите значение j, что приведет к потере пары, поэтому я бы создал if для этого условия.

Возможная коррекция:

#...
        else:  # got the match  arr[i] +arr[j] ==x
            print(arr[i], arr[j])

            if arr[j - 1] == arr[j] and arr[i + 1] == arr[i]:
                print(arr[i], arr[j])
                print(arr[i], arr[j])
                i += 1
                j -= 1

            elif arr[j - 1] == arr[j]:
                j -= 1

            elif arr[i + 1] == arr[i]:
                i += 1

            else:
                i += 1
                j -= 1