Programa de Python 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. 
 

# Python program to find a pair with the given difference
 
# The function assumes that the array is sorted
def findPair(arr,n):
 
    size = len(arr)
 
    # Initialize positions of two elements
    i,j = 0,1
 
    # Search for a pair
    while i < size and j < size:
 
        if i != j and arr[j]-arr[i] == n:
            print "Pair found (",arr[i],",",arr[j],")"
            return True
 
        elif arr[j] - arr[i] < n:
            j+=1
        else:
            i+=1
    print "No pair found"
    return False
 
# Driver function to test above function
arr = [1, 8, 30, 40, 100]
n = 60
findPair(arr, n)
 
# This code is contributed by Devesh Agrawal

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.

# Python program to find a pair with the given difference
 
def findPair(arr, size, n):
 
    # Initialising an empty hash table
    mp = {}
    for i in range(size):
        # Using array elements as hash keys
        # and entering them in Hash table.
        if arr[i] in mp.keys():
            mp[arr[i]] += 1
            # For n==0, checking if any element
            # is occurring more than 1 times or not
            if(n == 0 and mp[arr[i]] > 1):
                return True
        else:
            mp[arr[i]] = 1
     
    # Check if the difference is
    # still 0 with no element
    # occurring more than 1 times
    if(n == 0):
        return False
     
    for i in range(size):
        # Checking if arr[i]+n is present or not
        if n + arr[i] in mp.keys():
            print("Pair Found: " + "(" + str(arr[i]) + ", " + str(n + arr[i]) + ")")
            return True
     
    print("No such pair")
    return False
 
# Driver program to test above function
arr = [ 1, 8, 30, 40, 100 ]
size = len(arr)
n = 60
findPair(arr, size, n)
 
# 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!