Программа Javascript для поиска пары с заданной разницей

Опубликовано: 2 Сентября, 2022

Учитывая несортированный массив и число n, найдите, существует ли в массиве пара элементов, разность которых равна n.
Примеры:

Input: arr[] = {5, 20, 3, 2, 50, 80}, n = 78
Output: Pair Found: (2, 80)

Input: arr[] = {90, 70, 20, 80, 50}, n = 45
Output: No Such Pair

Самый простой способ — запустить два цикла: внешний цикл выбирает первый элемент (меньший элемент), а внутренний цикл ищет элемент, выбранный внешним циклом плюс n. Временная сложность этого метода составляет O(n^2).
Мы можем использовать сортировку и бинарный поиск, чтобы улучшить временную сложность до O(nLogn). Первый шаг — отсортировать массив в порядке возрастания. Как только массив отсортирован, пройдитесь по массиву слева направо и для каждого элемента arr[i] выполните двоичный поиск arr[i] + n в arr[i+1..n-1]. Если элемент найден, вернуть пару.
И первый, и второй шаги занимают O(nLogn). Таким образом, общая сложность составляет O (nLogn).
Второй шаг вышеприведенного алгоритма можно улучшить до O(n). Первый шаг остается прежним. Идея второго шага состоит в том, чтобы взять две индексные переменные i и j и инициализировать их как 0 и 1 соответственно. Теперь запустите линейный цикл. Если arr[j] – arr[i] меньше n, нам нужно искать большее значение arr[j], поэтому увеличиваем j. Если arr[j] – arr[i] больше n, нам нужно искать большее значение arr[i], поэтому увеличиваем i. Спасибо Aashish Barnwal за предложение этого подхода.
Следующий код предназначен только для второго шага алгоритма, он предполагает, что массив уже отсортирован.

Выход:

Pair Found: (40, 100)

Эффективный подход: для решения этой проблемы также можно использовать хеширование. Сначала мы создаем пустую хеш-таблицу HT. Затем мы просматриваем массив и используем элементы массива в качестве хеш-ключей и вводим их в HT. При обходе, если данная разница равна 0, мы проверим, встречается ли какой-либо элемент более одного раза или нет. Если n!=0, то мы снова просматриваем массив и ищем значение n + arr[i] в HT (хеш-таблице), так как разница между n+arr[i] и arr[i] равна n.
Ниже приведен код для вышеуказанного подхода.

Временная сложность: O(n)
Вспомогательное пространство: O(n)

Пожалуйста, обратитесь к полной статье о поиске пары с заданной разницей для получения более подробной информации!