Programa Javascript 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. 
 

<script>
 
       // JavaScript program for the above approach
 
       // The function assumes that the array is sorted
       function findPair(arr, size, n) {
           // Initialize positions of two elements
           let i = 0;
           let j = 1;
 
           // Search for a pair
           while (i < size && j < size) {
               if (i != j && arr[j] - arr[i] == n) {
                   document.write("Pair Found: (" + arr[i] + ", " +
                   arr[j] + ")");
                   return true;
               }
               else if (arr[j] - arr[i] < n)
                   j++;
               else
                   i++;
           }
 
           document.write("No such pair");
           return false;
       }
 
       // Driver program to test above function
 
       let arr = [1, 8, 30, 40, 100];
       let size = arr.length;
       let n = 60;
       findPair(arr, size, n);
 
 
   // This code is contributed by Potta Lokesh
  
   </script>

Producción:  

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.
 

<script>
     
 
    // JavaScript program for the above approach
 
    // The function assumes that the array is sorted
    function findPair(arr, size, n) {
         
        // Initializing unordered map
        let mp = new Map();
         
        for (let i = 0; i < size; i++) {
        // Using array elements as hash keys
        // and entering them in Hash table.
            if(!mp.has(arr[i]))
            mp.set(arr[i],1);
            else
            mp.set(arr[i],mp.get(arr[i])+1);
  
        // For n==0, checking if one element
        // is occurring more than 1 times
            if(mp.has(arr[i]))
            {    if (n==0 && mp.get(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 (let i = 0; i < size; i++)
        {
            // Checking if arr[i]+n is present or not
            if (mp.has(arr[i]+n))
            {
                val = n+arr[i];
                document.write("Pair Found: "+"(" + arr[i] + ", " + val + ")");
                return true;
            }
        }
 
        document.write("No such pair");
        return false;
    }
 
    // Driver program to test above function
 
    let arr = [1, 8, 30, 40, 100];
    let size = arr.length;
    let n = 60;
    findPair(arr, size, n);
     
    // This code is contributed by Pushpesh Raj.
     
</script>

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!