Programa en C++ para encontrar un par con la diferencia dada

Dada una array no ordenada y un número n, encuentre si existe un par de elementos en la array cuya diferencia es n. 
Ejemplos: 
 

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

El método más simple es ejecutar dos bucles, el bucle exterior selecciona el primer elemento (elemento más pequeño) y el bucle interior busca el elemento seleccionado por el bucle exterior más n. La complejidad temporal de este método es O(n^2).
Podemos usar la clasificación y la búsqueda binaria para mejorar la complejidad del tiempo a O (nLogn). El primer paso es ordenar la array en orden ascendente. Una vez que la array esté ordenada, recorra la array de izquierda a derecha, y para cada elemento arr[i], busque binariamente arr[i] + n en arr[i+1..n-1]. Si se encuentra el elemento, devuelve el par. 
Tanto el primer como el segundo paso toman O (nLogn). Entonces, la complejidad general es O (nLogn). 
El segundo paso del algoritmo anterior se puede mejorar a O(n). El primer paso sigue siendo el mismo. La idea para el segundo paso es tomar dos variables de índice i y j, inicializarlas como 0 y 1 respectivamente. Ahora ejecute un bucle lineal. Si arr[j] – arr[i] es más pequeño que n, debemos buscar un arr[j] mayor, por lo tanto, incremente j. Si arr[j] – arr[i] es mayor que n, debemos buscar un arr[i] mayor, por lo tanto, incremente i. Gracias a Aashish Barnwal por sugerir este enfoque. 
El siguiente código es solo para el segundo paso del algoritmo, asume que la array ya está ordenada. 
 

// C++ program to find a pair with the given difference
#include <bits/stdc++.h>
using namespace std;
 
// The function assumes that the array is sorted
bool findPair(int arr[], int size, int n)
{
    // Initialize positions of two elements
    int i = 0;
    int j = 1;
 
    // Search for a pair
    while (i < size && j < size)
    {
        if (i != j && arr[j] - arr[i] == n)
        {
            cout << "Pair Found: (" << arr[i] <<
                        ", " << arr[j] << ")";
            return true;
        }
        else if (arr[j]-arr[i] < n)
            j++;
        else
            i++;
    }
 
    cout << "No such pair";
    return false;
}
 
// Driver program to test above function
int main()
{
    int arr[] = {1, 8, 30, 40, 100};
    int size = sizeof(arr)/sizeof(arr[0]);
    int n = 60;
    findPair(arr, size, n);
    return 0;
}
 
// This is code is contributed by rathbhupendra

Pair Found: (40, 100)

Enfoque eficiente:  el hashing también se puede utilizar para resolver este problema. Primero creamos una tabla hash vacía HT. Luego recorremos la array y usamos los elementos de la array como claves hash y los ingresamos en HT. Durante el recorrido, si la diferencia dada es 0, verificaremos si algún elemento ocurre más de una vez o no. Si n!=0, entonces nuevamente Recorremos la array y buscamos el valor n + arr[i] en HT (tabla hash) ya que la diferencia entre n+arr[i] y arr[i] es n.
A continuación se muestra el código para el enfoque anterior.

// C++ program to find a pair with the given difference
#include <bits/stdc++.h>
using namespace std;
 
// The function assumes that the array is sorted
bool findPair(int arr[], int size, int n)
{
    // Using unordered_map for hashing
    unordered_map<int, int> mp;
    for (int i = 0; i < size; i++) {
        // Using array elements as hash keys
        // and entering them in Hash table.
        mp[arr[i]]++;
 
        // For n==0, checking if one element
        // is occurring more than 1 times
        if (n==0 && mp[arr[i]] > 1)
            return true;
    }
 
    // Check if the difference is
    // still 0 with no element
    // occurring more than 1 times
    if (n==0)
        return false;
 
    for (int i = 0; i <= size-1; i++)
    {
        // Checking if arr[i]+n is present or not
        if (mp[arr[i]+n])
        {
            cout << "Pair Found: "<< "(" << arr[i] << ", "<< n + arr[i] << ")";
            return true;
        }
    }
 
    cout << "No such pair";
    return false;
}
 
// Driver program to test above function
int main()
{
    int arr[] = { 1, 8, 30, 40, 100 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int n = 60;
    findPair(arr, size, n);
    return 0;
}
// This code is contributed by Pushpesh Raj.

Pair Found: (40, 100)

Complejidad temporal: O(n)
Espacio auxiliar: O(n)

¡ Consulte el artículo completo sobre Encuentre un par con la diferencia dada para obtener más detalles!