Programa C++ para contar pares con suma dada

Dada una array de enteros y un número ‘suma’, encuentra el número de pares de enteros en la array cuya suma es igual a ‘suma’.

Ejemplos:  

Input  :  arr[] = {1, 5, 7, -1}, 
          sum = 6
Output :  2
Pairs with sum 6 are (1, 5) and (7, -1)

Input  :  arr[] = {1, 5, 7, -1, 5}, 
          sum = 6
Output :  3
Pairs with sum 6 are (1, 5), (7, -1) &
                     (1, 5)         

Input  :  arr[] = {1, 1, 1, 1}, 
          sum = 2
Output :  6
There are 3! pairs with sum 2.

Input  :  arr[] = {10, 12, 10, 15, -1, 7, 6, 
                   5, 4, 2, 1, 1, 1}, 
          sum = 11
Output :  9

Complejidad del tiempo esperado O(n)
 

Solución ingenua: una solución simple es recorrer cada elemento y verificar si hay otro número en la array que se pueda agregar para dar la suma. 
 

// C++ implementation of simple method to find count of
// pairs with given sum.
#include <bits/stdc++.h>
using namespace std;
  
// Returns number of pairs in arr[0..n-1] with sum equal
// to 'sum'
int getPairsCount(int arr[], int n, int sum)
{
    int count = 0; // Initialize result
  
    // Consider all possible pairs and check their sums
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (arr[i] + arr[j] == sum)
                count++;
  
    return count;
}
  
// Driver function to test the above function
int main()
{
    int arr[] = { 1, 5, 7, -1, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 6;
    cout << "Count of pairs is "
         << getPairsCount(arr, n, sum);
    return 0;
}

Count of pairs is 3

Tiempo Complejidad: O(n ² ) 
Espacio Auxiliar: O(1)
  

Solución eficiente: 
una mejor solución es posible en tiempo O(n). A continuación se muestra el algoritmo: 

1. Cree un mapa para almacenar la frecuencia de cada número en la array. (Se requiere un solo recorrido)
2. En el siguiente recorrido, para cada elemento, compruebe si se puede combinar con cualquier otro elemento (¡aparte de él mismo!) para dar la suma deseada. Incremente el contador en consecuencia.
3. Después de completar el segundo recorrido, tendríamos el doble del valor requerido almacenado en el contador porque cada par se cuenta dos veces. Por lo tanto, divida la cuenta por 2 y regrese.

A continuación se muestra la implementación de la idea anterior: 
 

// C++ implementation of simple method to find count of
// pairs with given sum.
#include <bits/stdc++.h>
using namespace std;
  
// Returns number of pairs in arr[0..n-1] with sum equal
// to 'sum'
int getPairsCount(int arr[], int n, int sum)
{
    unordered_map<int, int> m;
  
    // Store counts of all elements in map m
    for (int i = 0; i < n; i++)
        m[arr[i]]++;
  
    int twice_count = 0;
  
    // iterate through each element and increment the
    // count (Notice that every pair is counted twice)
    for (int i = 0; i < n; i++) {
        twice_count += m[sum - arr[i]];
  
        // if (arr[i], arr[i]) pair satisfies the condition,
        // then we need to ensure that the count is
        // decreased by one such that the (arr[i], arr[i])
        // pair is not considered
        if (sum - arr[i] == arr[i])
            twice_count--;
    }
  
    // return the half of twice_count
    return twice_count / 2;
}
  
// Driver function to test the above function
int main()
{
    int arr[] = { 1, 5, 7, -1, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 6;
    cout << "Count of pairs is "
         << getPairsCount(arr, n, sum);
    return 0;
}

Count of pairs is 3

¡ Consulte el artículo completo sobre Contar pares con la suma dada para obtener más detalles!