Найти все пары чисел, сумма которых меньше S

#algorithm

#алгоритм

Вопрос:

Учитывая отсортированный массив a[0…n-1], найдите все пары чисел, сумма которых меньше S. Существует ли O (n) решение?

1. Учитывая, что вы работаете строго с парами чисел, да.

2. У вас есть три точки ... , которые также вычитаются 1 из n . Вы уверены, что вам нужны оба? Что такое nos ?

3. Джерри: Но в списке есть O (n ^ 2) пар.

Ответ №1:

Вы сейчас на собеседовании? Они скоро вернутся в комнату?

Поскольку все отсортировано, то одно из решений (если таковое имеется!) равно [0] и некоторым наибольшим [M]. Затем увеличьте нижний индекс от 0, а верхний индекс — от M. И некоторые подробности о том, какие из них использовать, а когда отклонить.

Редактировать — поскольку все еще может существовать O (n ^ 2) решений (например, если S более чем в два раза больше самой большой записи), хитрость будет заключаться в том, чтобы выразить решения в виде диапазонов. В противном случае простое перечисление займет слишком много времени.

1. M не упоминается в вопросе, но предполагая, что это так n-1 , утверждение «одно из решений (если таковое имеется!) равно [0] и [M]» неверно. Наиболее вероятным решением являются [0] и [1], которые легко могут находиться в диапазоне, в то время как [0] и [M] >= S. Диапазоны — отличная идея.

Ответ №2:

Это может помочь:

Найти два «нет» в массиве, сумма которого =X

Ответ №3:

Решение Дэвида должно сработать. Это будет O (N), даже если существует более N решений.

1) Начните с *ptr1 = a [0] и *ptr2 = a [X] <= S (X не всегда N-1)

2) Перемещайте ptr2 назад до тех пор, пока ptr1 ptr2 <= S.

— на данный момент ptr1 все индексы вплоть до ptr2 являются решениями.

3) Переместите ptr2 на один индекс назад, а ptr1 — на один индекс вверх

— повторить

Продолжайте, пока ptr1 > ptr2

Ответ №4:

Перечисление всех таких пар уже выполняется в O (n ^ 2) (обратите внимание, что это отличается от задачи суммирования ровно до S, поскольку в этом случае перечисление может быть выполнено в O (n), например «3 раза по паре (w, x), 1 раз по паре (y, z), …»

Ответ №5:

Решения O (n) не существует. Например, если у вас есть список, подобный этому: 1,2,3,4 … n и S = 3 * n, то сумма каждой пары меньше S. И количество пар, которые должны быть возвращены, равно n * (n-1)/2.