Programa Java para Count 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. 
 

// Java implementation of simple method to find count of
// pairs with given sum.
public class find {
    public static void main(String args[])
    {
        int[] arr = { 1, 5, 7, -1, 5 };
        int sum = 6;
        getPairsCount(arr, sum);
    }
  
    // Prints number of pairs in arr[0..n-1] with sum equal
    // to 'sum'
    public static void getPairsCount(int[] arr, int sum)
    {
  
        int count = 0; // Initialize result
  
        // Consider all possible pairs and check their sums
        for (int i = 0; i < arr.length; i++)
            for (int j = i + 1; j < arr.length; j++)
                if ((arr[i] + arr[j]) == sum)
                    count++;
  
        System.out.printf("Count of pairs is %d", count);
    }
}
// This program is contributed by Jyotsna

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: 
 

/* Java implementation of simple method to find count of
pairs with given sum*/
  
import java.util.HashMap;
  
class Test {
    static int arr[] = new int[] { 1, 5, 7, -1, 5 };
  
    // Returns number of pairs in arr[0..n-1] with sum equal
    // to 'sum'
    static int getPairsCount(int n, int sum)
    {
        HashMap<Integer, Integer> hm = new HashMap<>();
  
        // Store counts of all elements in map hm
        for (int i = 0; i < n; i++) {
  
            // initializing value to 0, if key not found
            if (!hm.containsKey(arr[i]))
                hm.put(arr[i], 0);
  
            hm.put(arr[i], hm.get(arr[i]) + 1);
        }
        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++) {
            if (hm.get(sum - arr[i]) != null)
                twice_count += hm.get(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 method to test the above function
    public static void main(String[] args)
    {
  
        int sum = 6;
        System.out.println(
            "Count of pairs is "
            + getPairsCount(arr.length, sum));
    }
}
// This code is contributed by Gaurav Miglani

Count of pairs is 3

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