Programa de Python 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. 
 

# Python3 implementation of simple method
# to find count of pairs with given sum.
  
# Returns number of pairs in arr[0..n-1]
# with sum equal to 'sum'
  
  
def getPairsCount(arr, n, sum):
  
    count = 0  # Initialize result
  
    # Consider all possible pairs
    # and check their sums
    for i in range(0, n):
        for j in range(i + 1, n):
            if arr[i] + arr[j] == sum:
                count += 1
  
    return count
  
  
# Driver function
arr = [1, 5, 7, -1, 5]
n = len(arr)
sum = 6
print("Count of pairs is",
      getPairsCount(arr, n, sum))
  
# This code is contributed by Smitha Dinesh Semwal

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: 
 

# Python 3 implementation of simple method
# to find count of pairs with given sum.
import sys
  
# Returns number of pairs in arr[0..n-1]
# with sum equal to 'sum'
  
  
def getPairsCount(arr, n, sum):
  
    m = [0] * 1000
  
    # Store counts of all elements in map m
    for i in range(0, n):
        m[arr[i]] += 1
  
    twice_count = 0
  
    # Iterate through each element and increment
    # the count (Notice that every pair is
    # counted twice)
    for i in range(0, n):
  
        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 -= 1
  
    # return the half of twice_count
    return int(twice_count / 2)
  
  
# Driver function
arr = [1, 5, 7, -1, 5]
n = len(arr)
sum = 6
  
print("Count of pairs is", getPairsCount(arr,
                                         n, sum))
  
# This code is contributed by
# Smitha Dinesh Semwal

Count of pairs is 3

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