Encuentra cuatro elementos que suman un valor dado | Conjunto 3 (mapa hash)

Dada una array de enteros, compruebe si existen cuatro elementos en diferentes índices de la array cuya suma es igual a un valor dado k. Por ejemplo, si la array dada es {1 5 1 0 6 0} y k = 7, entonces su función debe imprimir «SÍ» como (1+5+1+0=7).

Ejemplos:

Input  : arr[] = {1 5 1 0 6 0} 
             k = 7
Output : YES

Input :  arr[] = {38 7 44 42 28 16 10 37 
                  33 2 38 29 26 8 25} 
            k = 22
Output : NO

Hemos discutido diferentes soluciones en los siguientes dos conjuntos. Encuentra cuatro elementos que suman un valor dado | Conjunto 1 (solución n^3) Encuentra cuatro elementos que suman un valor dado | Conjunto 2 (Solución O(n^2Logn)) En esta publicación, se analiza una solución optimizada que funciona en O(n ² ) en promedio. La idea es crear un mapa hash para almacenar sumas de pares.

Loop i = 0 to n-1 :
 Loop j = i + 1 to n-1  
   calculate sum = arr[i] + arr[j]
     If (k-sum) exist in hash 
      a) Check in hash table for all
         pairs of indexes which form
         (k-sum).
      b) If there is any pair with no 
         no common indexes.
           return true 
    Else update hash table
    EndLoop;
EndLoop;

Implementación:

CPP

// C++ program to find if there exist 4 elements
// with given sum
#include <bits/stdc++.h>
using namespace std;
 
// function to check if there exist four
// elements whose sum is equal to k
bool findfour(int arr[], int n, int k)
{
    // map to store sum and indexes for
    // a pair sum
    unordered_map<int, vector<pair<int, int> > > hash;
 
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
 
            // calculate the sum of each pair
            int sum = arr[i] + arr[j];
 
            // if k-sum exist in map
            if (hash.find(k - sum) != hash.end()) {
                auto num = hash.find(k - sum);
                vector<pair<int, int> > v = num->second;
 
                // check for index coincidence as if
                // there is a common that means all
                // the four numbers are not from
                // different indexes and one of the
                // index is repeated
                for (int k = 0; k < num->second.size();
                     k++) {
 
                    pair<int, int> it = v[k];
 
                    // if all indexes are different then
                    // it means four number exist
                    // set the flag and break the loop
                    if (it.first != i && it.first != j
                        && it.second != i && it.second != j)
                        return true;
                }
            }
 
            // store the sum and index pair in hashmap
            hash[sum].push_back(make_pair(i, j));
        }
    }
    hash.clear();
    return false;
}
 
// Driver code
int main()
{
    int k = 7;
    int arr[] = { 1, 5, 1, 0, 6, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (findfour(arr, n, k))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

Producción

YES

Este artículo es una contribución de Niteesh Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

CPP

Deja una respuesta Cancelar la respuesta