Programa en C++ para encontrar un triplete que sume un valor dado

Dada una array y un valor, encuentre si hay un triplete en la array cuya suma es igual al valor dado. Si hay tal triplete presente en la array, imprima el triplete y devuelva verdadero. De lo contrario, devuelve falso.

Ejemplos: 
 

Entrada: array = {12, 3, 4, 1, 6, 9}, suma = 24; 
Salida: 12, 3, 9 
Explicación: Hay un triplete (12, 3 y 9) presente 
en la array cuya suma es 24. 
Entrada: array = {1, 2, 3, 4, 5}, suma = 9 
Salida: 5, 3, 1 
Explicación: Hay un triplete (5, 3 y 1) presente 
en el arreglo cuya suma es 9.

Método 1 : Este es el enfoque ingenuo para resolver el problema anterior.  

• Enfoque: un método simple es generar todos los tripletes posibles y comparar la suma de cada triplete con el valor dado. El siguiente código implementa este método simple usando tres bucles anidados.
• Algoritmo: 
  1. Dada una array de longitud n y una suma s
  2. Cree tres bucles anidados: el primer bucle se ejecuta de principio a fin (contador de bucle i), el segundo bucle se ejecuta desde i+1 hasta el final (contador de bucle j) y el tercer bucle se ejecuta desde j+1 hasta el final (contador de bucle k)
  3. El contador de estos bucles representa el índice de 3 elementos de los tripletes.
  4. Halla la suma de los elementos i, j y k. Si la suma es igual a la suma dada. Imprime el triplete y rompe.
  5. Si no hay triplete, imprima que no existe triplete.
• Implementación:

#include <bits/stdc++.h>
using namespace std;
  
// returns true if there is triplet with sum equal 
// to 'sum' present in A[]. Also, prints the triplet 
bool find3Numbers(int A[], int arr_size, int sum) 
{ 
    int l, r; 
  
    // Fix the first element as A[i] 
    for (int i = 0; i < arr_size - 2; i++)
    { 
  
        // Fix the second element as A[j] 
        for (int j = i + 1; j < arr_size - 1; j++)
        { 
  
            // Now look for the third number 
            for (int k = j + 1; k < arr_size; k++)
            { 
                if (A[i] + A[j] + A[k] == sum)
                { 
                    cout << "Triplet is " << A[i] <<
                        ", " << A[j] << ", " << A[k]; 
                    return true; 
                } 
            } 
        } 
    } 
  
    // If we reach here, then no triplet was found 
    return false; 
} 
  
/* Driver code */
int main() 
{ 
    int A[] = { 1, 4, 45, 6, 10, 8 }; 
    int sum = 22; 
    int arr_size = sizeof(A) / sizeof(A[0]); 
    find3Numbers(A, arr_size, sum); 
    return 0; 
} 
  
// This is code is contributed by rathbhupendra

Triplet is 4, 10, 8

• Análisis de Complejidad: 
  • Complejidad Temporal: O(n ³ ). 
    Hay tres bucles anidados que atraviesan la array, por lo que la complejidad del tiempo es O (n ^ 3)
  • Complejidad espacial: O(1). 
    Como no se requiere espacio adicional.

Método 2: este método utiliza la clasificación para aumentar la eficiencia del código. 

• Enfoque: al ordenar la array, se puede mejorar la eficiencia del algoritmo. Este enfoque eficiente utiliza la técnica de dos puntos . Atraviese la array y fije el primer elemento del triplete. Ahora use el algoritmo Two Pointers para encontrar si hay un par cuya suma es igual a x – array[i]. El algoritmo de dos punteros toma un tiempo lineal, por lo que es mejor que un bucle anidado.
• Algoritmo: 
  1. Ordenar la array dada.
  2. Recorra la array y fije el primer elemento del posible triplete, arr[i].
  3. Luego fije dos punteros, uno en i + 1 y el otro en n – 1. Y mire la suma, 
     1. Si la suma es menor que la suma requerida, incremente el primer puntero.
     2. De lo contrario, si la suma es mayor, disminuya el puntero final para reducir la suma.
     3. De lo contrario, si la suma de los elementos en dos punteros es igual a la suma dada, imprima el triplete y rompa.
• Implementación:

// C++ program to find a triplet
#include <bits/stdc++.h>
using namespace std;
  
// returns true if there is triplet with sum equal
// to 'sum' present in A[]. Also, prints the triplet
bool find3Numbers(int A[], int arr_size, int sum)
{
    int l, r;
  
    /* Sort the elements */
    sort(A, A + arr_size);
  
    /* Now fix the first element one by one and find the
       other two elements */
    for (int i = 0; i < arr_size - 2; i++) {
  
        // To find the other two elements, start two index
        // variables from two corners of the array and move
        // them toward each other
        l = i + 1; // index of the first element in the
        // remaining elements
  
        r = arr_size - 1; // index of the last element
        while (l < r) {
            if (A[i] + A[l] + A[r] == sum) {
                printf("Triplet is %d, %d, %d", A[i],
                       A[l], A[r]);
                return true;
            }
            else if (A[i] + A[l] + A[r] < sum)
                l++;
            else // A[i] + A[l] + A[r] > sum
                r--;
        }
    }
  
    // If we reach here, then no triplet was found
    return false;
}
  
/* Driver program to test above function */
int main()
{
    int A[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 22;
    int arr_size = sizeof(A) / sizeof(A[0]);
  
    find3Numbers(A, arr_size, sum);
  
    return 0;
}

Triplet is 4, 8, 10

• Análisis de Complejidad: 
  • Complejidad del tiempo: O(N^2). 
    Solo hay dos bucles anidados que atraviesan la array, por lo que la complejidad del tiempo es O (n ^ 2). El algoritmo de dos punteros toma un tiempo O (n) y el primer elemento se puede arreglar usando otro recorrido anidado.
  • Complejidad espacial: O(1). 
    Como no se requiere espacio adicional.

Método 3 : Esta es una solución basada en Hashing. 

• Enfoque: este enfoque utiliza espacio adicional pero es más simple que el enfoque de dos puntos. Ejecute dos bucles, el bucle externo de principio a fin y el bucle interno desde i+1 hasta el final. Cree un hashmap o configure para almacenar los elementos entre i+1 y j-1. Entonces, si la suma dada es x, verifique si hay un número en el conjunto que sea igual a x – arr[i] – arr[j]. En caso afirmativo, imprima el triplete. 
   
• Algoritmo: 
  1. Atraviesa la array de principio a fin. (contador de bucle i)
  2. Cree un HashMap o configúrelo para almacenar pares únicos.
  3. Ejecute otro ciclo desde i+1 hasta el final de la array. (contador de bucle j)
  4. Si hay un elemento en el conjunto que es igual a x-arr[i] – arr[j], imprima el triplete (arr[i], arr[j], x-arr[i]-arr[j] ) y romper
  5. Inserta el j-ésimo elemento en el conjunto.
• Implementación:

// C++ program to find a triplet using Hashing
#include <bits/stdc++.h>
using namespace std;
  
// returns true if there is triplet with sum equal
// to 'sum' present in A[]. Also, prints the triplet
bool find3Numbers(int A[], int arr_size, int sum)
{
    // Fix the first element as A[i]
    for (int i = 0; i < arr_size - 2; i++) 
    {
  
        // Find pair in subarray A[i+1..n-1]
        // with sum equal to sum - A[i]
        unordered_set<int> s;
        int curr_sum = sum - A[i];
        for (int j = i + 1; j < arr_size; j++) 
        {
            if (s.find(curr_sum - A[j]) != s.end()) 
            {
                printf("Triplet is %d, %d, %d", A[i],
                       A[j], curr_sum - A[j]);
                return true;
            }
            s.insert(A[j]);
        }
    }
  
    // If we reach here, then no triplet was found
    return false;
}
  
/* Driver program to test above function */
int main()
{
    int A[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 22;
    int arr_size = sizeof(A) / sizeof(A[0]);
  
    find3Numbers(A, arr_size, sum);
  
    return 0;
}

Producción:

Triplet is 4, 8, 10

Complejidad temporal: O(N^2) 
Espacio auxiliar: O(N)
 

Consulte el artículo completo sobre Encuentre un triplete que sume un valor dado para obtener más detalles.