Compruebe si existen dos elementos en una array cuya suma es igual a la suma del resto de la array

Tenemos una array de enteros y tenemos que encontrar dos de esos elementos en la array de manera que la suma de estos dos elementos sea igual a la suma del resto de los elementos de la array. 

Ejemplos: 

Input  : arr[] = {2, 11, 5, 1, 4, 7}
Output : Elements are 4 and 11
Note that 4 + 11 = 2 + 5 + 1 + 7

Input  : arr[] = {2, 4, 2, 1, 11, 15}
Output : Elements do not exist 

Una solución simple es considerar cada par uno por uno, encontrar su suma y comparar la suma con la suma del resto de los elementos. Si encontramos un par cuya suma es igual al resto de elementos, imprimimos el par y devolvemos verdadero. La complejidad temporal de esta solución es O(n ³ )

Una solución eficiente es encontrar la suma de todos los elementos de la array. Sea esta suma «suma». Ahora la tarea se reduce a encontrar un par con suma igual a suma/2. 

Otra optimización es que un par puede existir solo si la suma de toda la array es par porque básicamente lo estamos dividiendo en dos partes con la misma suma.

1. Encuentre la suma de toda la array. Sea esta suma «suma» 
2. Si la suma es impar, devuelve falso. 
3. Encuentre un par con una suma igual a «sum/2» utilizando el método basado en hashing discutido aquí como método 2. Si se encuentra un par, imprímalo y devuelva verdadero. 
4. Si no existe ningún par, devuelve falso.

A continuación se muestra la implementación de los pasos anteriores.

// C++ program to find whether two elements exist
// whose sum is equal to sum of rest of the elements.
#include<bits/stdc++.h>
using namespace std;
 
// Function to check whether two elements exist
// whose sum is equal to sum of rest of the elements.
bool checkPair(int arr[],int n)
{
    // Find sum of whole array
    int sum = 0;
    for (int i=0; i<n; i++)
        sum += arr[i];
 
    // If sum of array is not even than we can not
    // divide it into two part
    if (sum%2 != 0)
        return false;
 
    sum = sum/2;
 
    // For each element arr[i], see if there is
    // another element with value sum - arr[i]
    unordered_set<int> s;
    for (int i=0; i<n; i++)
    {
        int val = sum-arr[i];
 
        // If element exist than return the pair
        if (s.find(val) != s.end())
        {
            printf("Pair elements are %d and %d\n",
                                    arr[i], val);
            return true;
        }
 
        s.insert(arr[i]);
    }
 
    return false;
}
 
// Driver program.
int main()
{
    int arr[] = {2, 11, 5, 1, 4, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    if (checkPair(arr, n) == false)
       printf("No pair found");
    return 0;
}

// Java program to find whether two elements exist
// whose sum is equal to sum of rest of the elements.
import java.util.*;
 
class GFG
{
     
    // Function to check whether two elements exist
    // whose sum is equal to sum of rest of the elements.
    static boolean checkPair(int arr[], int n)
    {
        // Find sum of whole array
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
        }
 
        // If sum of array is not even than we can not
        // divide it into two part
        if (sum % 2 != 0)
        {
            return false;
        }
 
        sum = sum / 2;
 
        // For each element arr[i], see if there is
        // another element with value sum - arr[i]
        HashSet<Integer> s = new HashSet<Integer>();
        for (int i = 0; i < n; i++)
        {
            int val = sum - arr[i];
 
            // If element exist than return the pair
            if (s.contains(val) &&
                val == (int) s.toArray()[s.size() - 1])
            {
                System.out.printf("Pair elements are %d and %d\n",
                        arr[i], val);
                return true;
            }
            s.add(arr[i]);
        }
        return false;
    }
 
    // Driver program.
    public static void main(String[] args)
    {
        int arr[] = {2, 11, 5, 1, 4, 7};
        int n = arr.length;
        if (checkPair(arr, n) == false)
        {
            System.out.printf("No pair found");
        }
    }
}
 
/* This code contributed by PrinciRaj1992 */

# Python3 program to find whether
# two elements exist whose sum is
# equal to sum of rest of the elements.
 
# Function to check whether two
# elements exist whose sum is equal
# to sum of rest of the elements.
def checkPair(arr, n):
    s = set()
    sum = 0
 
    # Find sum of whole array
    for i in range(n):
        sum += arr[i]
     
    # / If sum of array is not
    # even than we can not
    # divide it into two part
    if sum % 2 != 0:
        return False
    sum = sum / 2
 
    # For each element arr[i], see if
    # there is another element with
    # value sum - arr[i]
    for i in range(n):
        val = sum - arr[i]
        if arr[i] not in s:
            s.add(arr[i])
             
        # If element exist than
        # return the pair
        if val in s:
            print("Pair elements are",
                   arr[i], "and", int(val))
 
# Driver Code
arr = [2, 11, 5, 1, 4, 7]
n = len(arr)
if checkPair(arr, n) == False:
    print("No pair found")
 
# This code is contributed
# by Shrikant13

// C# program to find whether two elements exist
// whose sum is equal to sum of rest of the elements.
using System;
using System.Collections.Generic;
 
class GFG
{
     
    // Function to check whether two elements exist
    // whose sum is equal to sum of rest of the elements.
    static bool checkPair(int []arr, int n)
    {
        // Find sum of whole array
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
        }
 
        // If sum of array is not even than we can not
        // divide it into two part
        if (sum % 2 != 0)
        {
            return false;
        }
 
        sum = sum / 2;
 
        // For each element arr[i], see if there is
        // another element with value sum - arr[i]
        HashSet<int> s = new HashSet<int>();
        for (int i = 0; i < n; i++)
        {
            int val = sum - arr[i];
 
            // If element exist than return the pair
            if (s.Contains(val))
            {
                Console.Write("Pair elements are {0} and {1}\n",
                        arr[i], val);
                return true;
            }
            s.Add(arr[i]);
        }
        return false;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int []arr = {2, 11, 5, 1, 4, 7};
        int n = arr.Length;
        if (checkPair(arr, n) == false)
        {
            Console.Write("No pair found");
        }
    }
}
 
// This code contributed by Rajput-Ji

<?php
// PHP program to find whether two elements exist
// whose sum is equal to sum of rest of the elements.
 
// Function to check whether two elements exist
// whose sum is equal to sum of rest of the elements.
function checkPair(&$arr, $n)
{
    // Find sum of whole array
    $sum = 0;
    for ($i = 0; $i < $n; $i++)
        $sum += $arr[$i];
 
    // If sum of array is not even than we
    // can not divide it into two part
    if ($sum % 2 != 0)
        return false;
 
    $sum = $sum / 2;
 
    // For each element arr[i], see if there is
    // another element with value sum - arr[i]
    $s = array();
    for ($i = 0; $i < $n; $i++)
    {
        $val = $sum - $arr[$i];
 
        // If element exist than return the pair
        if (array_search($val, $s))
        {
            echo "Pair elements are " . $arr[$i] .
                 " and " . $val . "\n";
                                     
            return true;
        }
 
        array_push($s, $arr[$i]);
    }
 
    return false;
}
 
// Driver Code
$arr = array(2, 11, 5, 1, 4, 7);
$n = sizeof($arr);
if (checkPair($arr, $n) == false)
    echo "No pair found";
 
// This code is contributed by ita_c
?>

<script>
 
// Javascript program to find
// whether two elements exist
// whose sum is equal to sum of rest
// of the elements.   
     
    // Function to check whether
    // two elements exist
    // whose sum is equal to sum of
    // rest of the elements.
    function checkPair(arr,n)
    {
        // Find sum of whole array
        let sum = 0;
        for (let i = 0; i < n; i++)
        {
            sum += arr[i];
        }
   
        // If sum of array is not even than we can not
        // divide it into two part
        if (sum % 2 != 0)
        {
            return false;
        }
   
        sum = Math.floor(sum / 2);
   
        // For each element arr[i], see if there is
        // another element with value sum - arr[i]
        let s = new Set();
        for (let i = 0; i < n; i++)
        {
            let val = sum - arr[i];
   
            // If element exist than return the pair
             
            if(!s.has(arr[i]))
            {
                s.add(arr[i])
            }
             
            if (s.has(val) )
            {
                document.write("Pair elements are "+
                        arr[i]+" and "+ val+"<br>");
                return true;
            }
            s.add(arr[i]);
        }
        return false;
    }
    // Driver program.
    let arr=[2, 11, 5, 1, 4, 7];
    let n = arr.length;
    if (checkPair(arr, n) == false)
    {
        document.write("No pair found");
    }
     
    // This code is contributed by rag2127
     
</script>

Pair elements are 4 and 11

Complejidad temporal : O(n) . unordered_set se implementa usando hashing. La búsqueda e inserción de hash de complejidad temporal se asume como O(1) aquí.
Espacio Auxiliar: O(n)

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.