Programa en C++ para encontrar un triplete tal que la suma de dos sea igual al tercer elemento

Dada una array de números enteros, debe encontrar tres números tales que la suma de dos elementos sea igual al tercer elemento.
Ejemplos:

Input: {5, 32, 1, 7, 10, 50, 19, 21, 2}
Output: 21, 2, 19

Input: {5, 32, 1, 7, 10, 50, 19, 21, 0}
Output: no such triplet exist

Fuente de la pregunta: experiencia de entrevista con Arcesium | Conjunto 7 (En el campus para prácticas)

Enfoque simple: ejecute tres bucles y verifique si existe un triplete tal que la suma de dos elementos sea igual al tercer elemento.
Complejidad del tiempo : O(n^3)
Enfoque eficiente: La idea es similar a Encontrar un triplete que sume un valor dado.

• Primero ordene la array dada.
• Comience a fijar el mayor elemento de tres desde atrás y recorra la array para encontrar los otros dos números que suman el tercer elemento.
• Tome dos punteros j (desde el frente) y k (inicialmente i-1) para encontrar el menor de los dos números y desde i-1 para encontrar el mayor de los dos números restantes
• Si la suma de ambos números sigue siendo menor que A[i], entonces necesitamos aumentar el valor de la suma de dos números, aumentando así el puntero j, para aumentar el valor de A[j] + A[ k] .
• Si la suma de ambos números es mayor que A[i], entonces debemos disminuir el valor de la suma de dos números, por lo tanto, disminuir el puntero k para disminuir el valor total de A[j] + A[k ] .

La imagen de abajo es una ejecución en seco del enfoque anterior:

A continuación se muestra la implementación del enfoque anterior:

// C++ program to find three numbers
// such that sum of two makes the
// third element in array
#include <bits/stdc++.h>
using namespace std;
  
// Utility function for finding
// triplet in array
void findTriplet(int arr[], int n)
{
    // Sort the array
    sort(arr, arr + n);
  
    // For every element in arr check 
    // if a pair exist(in array) whose
    // sum is equal to arr element
    for (int i = n - 1; i >= 0; i--) 
    {
        int j = 0;
        int k = i - 1;
  
        // Iterate forward and backward to 
        // find the other two elements
        while (j < k) 
        {
            // If the two elements sum is
            // equal to the third element
            if (arr[i] == arr[j] + arr[k]) 
            {
                // Pair found
                cout << "numbers are " << arr[i] << 
                        " " << arr[j] << " " << 
                        arr[k] << endl;
                return;
            }
  
            // If the element is greater than
            // sum of both the elements, then try
            // adding a smaller number to reach the
            // equality
            else if (arr[i] > arr[j] + arr[k])
                j += 1;
  
            // If the element is smaller, then
            // try with a smaller number
            // to reach equality, so decrease K
            else
                k -= 1;
        }
    }
  
    // No such triplet is found in array
    cout << "No such triplet exists";
}
  
// Driver code
int main()
{
    int arr[] = {5, 32, 1, 7, 10, 
                 50, 19, 21, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    findTriplet(arr, n);
    return 0;
}

Producción:  

numbers are 21 2 19

Complejidad del tiempo : O(N^2)

Otro enfoque: la idea es similar al enfoque anterior.

1. Ordenar la array dada.
2. Inicie un bucle anidado, fijando el primer elemento i (de 0 a n-1) y moviendo el otro j (de i+1 a n-1).
3. Tome la suma de ambos elementos y búsquelo en la array restante usando la búsqueda binaria.

// C++ program to find three numbers
// such that sum of two makes the
// third element in array
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
  
// Function to perform binary search
bool search(int sum, int start, 
            int end, int arr[])
{
    while (start <= end) 
    {
        int mid = (start + end) / 2;
        if (arr[mid] == sum) 
        {
            return true;
        }
        else if (arr[mid] > sum) 
        {
            end = mid - 1;
        }
        else 
        {
            start = mid + 1;
        }
    }
    return false;
}
  
// Function to find the triplets
void findTriplet(int arr[], int n)
{
    // Sorting the array
    sort(arr, arr + n);
  
    // Initialising nested loops
    for (int i = 0; i < n; i++) 
    {
        for (int j = i + 1; j < n; j++) 
        {
            // Finding the sum of the numbers
            if (search((arr[i] + arr[j]), 
                j, n - 1, arr)) 
            {
                // Printing out the first triplet
                cout << "Numbers are: " << arr[i] << 
                        " " << arr[j] << " " << 
                        (arr[i] + arr[j]);
                return;
            }
        }
    }
    // If no such triplets are found
    cout << "No such numbers exist" << endl;
}
  
// Driver code
int main()
{
    int arr[] = {5, 32, 1, 7, 10, 
                 50, 19, 21, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    findTriplet(arr, n);
    return 0;
}
// This code is contributed by Sarthak Delori

Complejidad del tiempo: O(N^2*log N)

Complejidad espacial:   O(1)

Consulte el artículo completo sobre Encontrar un triplete tal que la suma de dos sea igual al tercer elemento para obtener más detalles.