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

<script>
 
 // Naive solution to find if there is a
// pair in A[0..N-1] with given sum.
 
function isPairSum(A, N, X)
{
        for (var i = 0; i < N-1; i++)
        {
            for (var j = i+1; j < N; j++)
            {
                // as equal i and j means same element
                if (i == j)
                    continue;
 
                // pair exists
                if (A[i] + A[j] == X)
                    return 1;
 
                // as the array is sorted
                if (A[i] + A[j] > X)
                    break;
            }
        }
 
        // No pair found with given sum.
        return 0;
}
 
 
     
        var arr=[ 3, 5, 9, 2, 8, 10, 11 ];
         
        // value to search
        var val = 17;
     
        // size of the array
        var arrSize = 7;
     
        // Function call
        document.write(isPairSum(arr, arrSize, val));
 
</script>

1

Complejidad Temporal:  O(n ² ).

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. 

<script>
// Two pointer technique based solution to find
// if there is a pair in A[0..N-1] with a given sum.
function isPairSum(A, N, X)
{
 
    // represents first pointer
    var i = 0;
 
    // represents second pointer
    var 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++
        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 false;
}
 
// Driver code
 
    // array declaration
    var arr = [ 3, 5, 9, 2, 8, 10, 11 ];
     
    // value to search
    var val = 17;
     
    // size of the array
    var arrSize =7;
     
    // Function call
    document.write(isPairSum(arr, arrSize, val));
     
    // This Code is Contributed by Harshit Srivastava
 
   </script>

1

Ilustración : 
 

Complejidad de tiempo:  O(n)

Complejidad espacial : 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!