Cuente el número de pares distintos cuya suma existe en la array dada

Dada una array de N enteros positivos. Cuente el número de pares cuya suma existe en la array dada. Mientras que los pares repetidos no se contarán de nuevo. Y no podemos hacer un par usando el mismo elemento de posición. Por ejemplo: (2, 1) y (1, 2) serán considerados como un solo par. Lea atentamente todos los ejemplos. 

Ejemplos:

Input : arr[] = {1, 2, 3, 5, 10}
Output : 2
Explanation : Here there are two such pairs:
(1 + 2) = 3, (2 + 3) = 5.
Note : Here we can't take pair (5, 5) as 
we can see 5 is not coming twice

Input : arr[] = {1, 5, 6, 4, -1, 5} 
Output : 4
Explanation : (1 + 5) = 6, (1 + 4) = 5, 
(5 + -1) = 4, (6 + -1) = 5
Note : Here (1, 5) comes twice will be 
considered as only one pair. 

Input : arr[] = {5, 5, 5, 5, 10} 
Output : 1
Explanation : (5 + 5) = 10
Note : Here (5, 5) comes twice will be
considered as only one pair. 

La idea es hacer un mapa de pares para encontrar elementos únicos. Primero almacenamos elementos y sus conteos en un mapa. Luego recorremos los elementos del arreglo, para cada par de elementos (arr[i], arr[j]), verificamos si (arr[i] + arr[j]) existe en el arreglo. Si existe, verificamos si ya está contado usando el mapa de pares. Si aún no se cuenta, entonces incrementamos el conteo. 

Implementación:

// C++ implementation to find count of unique pairs
// whose sum exists in given array
#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)
{
    // Store counts of all elements in map m
    // to find pair (arr[i], sum-arr[i])
    // because (arr[i]) + (sum - arr[i]) = sum
    map<int, int> m;
    for (int i = 0; i < n; i++)
        m[arr[i]]++;
 
    // To remove duplicate items we use result map
    map<pair<int, int>, int> pairs;
 
    int count = 0; // Initialize result
 
    // Consider all pairs
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
 
            // If sum of current pair exists
            if (m[arr[i] + arr[j]] > 0 &&
                pairs[{ arr[i], arr[j] }] == 0) {
                count++;
            }
 
            // Insert current pair both ways to avoid
            // duplicates.
            pairs[{ arr[i], arr[j] }]++;
            pairs[{ arr[j], arr[i] }]++;
        }
    }
    return count;
}
 
// Driver function to test the above function
int main()
{
    int arr[] = { 1, 5, 6, 4, -1, 5, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << getPairsCount(arr, n);
    return 0;
}

# Python3 implementation to find count
# of unique pairs whose sum exists in
# given array
 
# Returns number of pairs in arr[0..n-1]
# with sum equal to 'sum'
def getPairsCount(arr, n):
 
    # Store counts of all elements in map m
    # to find pair (arr[i], sum-arr[i])
    # because (arr[i]) + (sum - arr[i]) = sum
    m = dict()
    for i in range(n):
        m[arr[i]] = m.get(arr[i], 0) + 1
 
    # To remove duplicate items
    # we use result map
    pairs1 = dict()
 
    count = 0 # Initialize result
 
    for i in range(n):
        for j in range(i + 1, n):
            l = arr[i] + arr[j]
            tp = (arr[i], arr[j])
 
            if l in m.keys():
 
                if tp not in pairs1.keys():
 
                    count += 1
            pairs1[(arr[i], arr[j])] = 1
            pairs1[(arr[j], arr[i])] = 1
 
    return count
 
# Driver Code
arr = [1, 5, 6, 4, -1, 5, 10]
n = len(arr)
 
print(getPairsCount(arr, n))
 
# This code is contributed by Mohit Kumar

6

Este artículo es una contribución de Harshit Agrawal . 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.