Алгоритм поиска пары чисел в массиве целых чисел, сумма которых равна

Question

Алгоритм поиска пары чисел в массиве целых чисел, сумма которых равна.ex {1 2 3 4 6}

здесь {3 2} {4 1} должен быть выходом, потому что сумма равна 3 + 2 = 5, 4 + 1 = 5.

Здесь главным является сложность O (n).Пожалуйста, помогите мне, если мы найдем какие-либо решения для этого?

Answer 1

Вы уверены, что проблема вообще решаема в O (n)?

Представьте себе случай, когда входная последовательность просто {0, 0, 0, 0, 0, 0, ..., 0}. Здесь каждые две пары удовлетворяют условию. Просто перечислить все пары уже, по крайней мере, O (n ^ 2).

Answer 2

Я думаю, что это возможно:

вам нужен второй массив tmp = {} с длиной суммы.

sum = 5
array = {1,2,3,4,6}
for every i in array{
    if i>=sum:
        continue
    if tmp[i] != 0 {
        output {i,(sum-i)}
        tmp[i] = 0
        continue
    }

    tmp[sum-i] := i
}

вот и все.так просто и с O (n)

cons:

1. он не найдет пару типа {5,0}, поэтому вы должны использовать реальные Integer-Objects для проверкив строке 6 против NULL и присвойте NULL в строке 8, пары
2. с отрицательным числом не будут работать.

Answer 3

Кажется, что проблема заключается в отсутствии некоторых ограничений, которые были бы полезны.Первое, что я хотел бы предложить, каждое целое число в массиве должно быть отличным.По крайней мере, выходные данные должны быть уникальными парами.

Другим ограничением, которое может или не может применяться к определенной проблемной области, является отсортированный массив.Это ограничение, если оно истинно, предполагает простой алгоритм.Начните 2 указателя, левый и правый, их соответствующие концы.Если сумма совпадает, выведите ее, увеличьте влево и уменьшите вправо.Если не совпадает, уменьшите правый указатель, если сумма слишком велика, или увеличьте левое (слишком мало).Продолжайте регулировать влево и вправо, пока они не пересечутся где-то посередине.

Для несортированного массива.Создайте хеш-таблицу, вставьте все целые числа.Пройдите по массиву еще раз, на этот раз ищите в хэш-таблице значение, чтобы удовлетворить требуемую сумму.Если хеш-функция идеальна (что может быть сложно достичь), тогда ожидаемое время выполнения равно O (n).

Answer 4

Я не уверен, возможно ли это сделать эффективно.

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

Подумайте об алгоритме поиска. наименее сложный, линейный (последовательный) поиск имеет сложность O (n). Это просто для прохождения массива. Если вы знаете сумму, которую вы ожидаете, случай аналогичен, и на самом деле вам нужно выполнить линейный поиск. За все остальное вы получаете более высокую сложность.

Но в вашем случае вы не знаете сумму, поэтому вам придется проходить более одного раза. Моя голова говорит, что это O (n log n) или O (n ^ 2).

Возможно, может быть решение, которое использует больше структур данных, возможно, таблицу суммирования (двумерный массив ???), но вероятность существования такого решения мала.