Programa Java 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.
import java.io.*;
 
class GFG {
    public static void main(String[] args)
    {
        int arr[] = { 3, 5, 9, 2, 8, 10, 11 };
        int val = 17;
 
        System.out.println(isPairSum(arr, arr.length, val));
    }
     
    private static int isPairSum(int A[], int N, int X)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                // 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;
    }
}

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. 

import java.io.*;
 
class GFG
{
     // Two pointer technique based solution to find
    // if there is a pair in A[0..N-1] with a given sum.
    public static int isPairSum(int A[], int N, int X)
    {
        // represents first pointer
        int i = 0;
 
        // represents second pointer
        int j = N - 1;
 
        while (i < j) {
 
            // If we find a pair
            if (A[i] + A[j] == X)
                return 1;
 
            // If sum of elements at current
            // pointers is less, we move towards
            // higher values by doing i++
            else if (A[i] + A[j] < X)
                i++;
 
            // If sum of elements at current
            // pointers is more, we move towards
            // lower values by doing j--
            else
                j--;
        }
        return 0;
    }
   
    // Driver code
    public static void main(String[] args)
    {
        // array declaration
        int arr[] = { 3, 5, 9, 2, 8, 10, 11 };
         
        // value to search
        int val = 17;
       
        // size of the array
        int arrSize = arr.length;
       
        // Function call
        System.out.println(isPairSum(arr, arrSize, val));
    }
}

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!