Programa Python3 para la técnica de dos punteros

Dos punteros es realmente una técnica fácil y efectiva que se usa típicamente para buscar pares en una array ordenada.
Dada una array ordenada A (ordenada en orden ascendente), que tiene N enteros, encuentre si existe algún par de elementos (A[i], A[j]) tal que su suma sea igual a X.

Veamos la solución ingenua .  

# Naive solution to find if there is a
# pair in A[0..N-1] with given sum.
def isPairSum(A, N, X):
 
    for i in range(N):
        for j in range(N):
 
            # as equal i and j means same element
            if(i == j):
                continue
 
            # pair exists
            if (A[i] + A[j] == X):
                return True
 
            # as the array is sorted
            if (A[i] + A[j] > X):
                break
             
    # No pair found with given sum
    return 0
 
# Driver code
arr = [3, 5, 9, 2, 8, 10, 11]
val = 17
 
print(isPairSum(arr, len(arr), val))
 
# This code is contributed by maheshwaripiyush9

1

Complejidad temporal:  O(n ² )

Espacio Auxiliar: O(1)

Ahora veamos cómo funciona la técnica de dos puntos. Tomamos dos punteros, uno que representa el primer elemento y otro que representa el último elemento de la array, y luego sumamos los valores guardados en ambos punteros. Si su suma es menor que X, desplazamos el puntero izquierdo hacia la derecha o si su suma es mayor que X, desplazamos el puntero derecho hacia la izquierda para acercarnos a la suma. Seguimos moviendo los punteros hasta obtener la suma como X. 

# Two pointer technique based solution to find
# if there is a pair in A[0..N-1] with a given sum.
def isPairSum(A, N, X):
 
    # represents first pointer
    i = 0
 
    # represents second pointer
    j = N - 1
 
    while(i < j):
       
        # If we find a pair
        if (A[i] + A[j] == X):
            return True
 
        # If sum of elements at current
        # pointers is less, we move towards
        # higher values by doing i += 1
        elif(A[i] + A[j] < X):
            i += 1
 
        # If sum of elements at current
        # pointers is more, we move towards
        # lower values by doing j -= 1
        else:
            j -= 1
    return 0
 
# array declaration
arr = [3, 5, 9, 2, 8, 10, 11]
 
# value to search
val = 17
 
print(isPairSum(arr, len(arr), val))
 
# This code is contributed by maheshwaripiyush9.

1

Ilustración : 
 

Complejidad de tiempo:  O(n)

Espacio Auxiliar: O(1) ya que usa espacio constante

¿Como funciona esto?  
Básicamente, el algoritmo utiliza el hecho de que la array de entrada está ordenada. Comenzamos la suma de los valores extremos (el más pequeño y el más grande) y movemos condicionalmente ambos punteros. Movemos el puntero izquierdo i cuando la suma de A[i] y A[j] es menor que X. No perdemos ningún par porque la suma ya es menor que X. La misma lógica se aplica para el puntero derecho j.

Más problemas basados ​​en la técnica de dos punteros. 

• Encuentre el par más cercano de dos arrays ordenadas
• Encuentre el par en la array cuya suma es más cercana a x
• Encuentra todos los tripletes con suma cero
• Encuentre un triplete que sume un valor dado
• Encuentra un triplete tal que la suma de dos sea igual al tercer elemento
• Encuentra cuatro elementos que suman un valor dado

¡ Consulte el artículo completo sobre la técnica de dos punteros para obtener más detalles!