Cuente los pares de dos arrays que tengan una suma igual a K

Dado un entero K y dos arrays A1 y A2 , la tarea es devolver el número total de pares (un elemento de A1 y un elemento de A2  ) con una suma igual a K.

Nota: las arrays pueden tener elementos duplicados. Consideramos cada par como diferente, la única restricción es que un elemento (de cualquier array) puede participar solo en un par. Por ejemplo, A1[] = {3, 3}, A2[] = {4, 4} y K = 7, consideramos solo dos pares (3, 4) y (3, 4)

Ejemplos:

Input: A1[] = {1, 1, 3, 4, 5, 6, 6}, A2[] = {1, 4, 4, 5, 7}, K = 10 
Output: 4 
All possible pairs are {3, 7}, {4, 6}, {5, 5} and {4, 6}

Input: A1[] = {1, 10, 13, 15}, A2[] = {3, 3, 12, 4}, K = 13 
Output: 2 

Acercarse:  

• Cree un mapa de los elementos de la array A1 .
• Para cada elemento en la array A2 , verifique si temp = K – A2[i] existe en el mapa creado en el paso anterior.
• Si map[temp] > 0 entonces incrementa el resultado en 1 y disminuye map[temp] en 1 .
• Imprime el conteo total al final.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of above approach.
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of pairs
// having sum equal to K
int countPairs(int A1[], int A2[]
                  , int n1, int n2, int K)
{
    // Initialize pairs to 0
    int res = 0;
 
    // create map of elements of array A1
    unordered_map<int, int> m;
    for (int i = 0; i < n1; ++i)
        m[A1[i]]++;
 
    // count total pairs
    for (int i = 0; i < n2; ++i) {
        int temp = K - A2[i];
 
        if (m[temp] != 0) {
            res++;
 
            // Every element can be part
            // of at most one pair.
            m[temp]--;
        }
    }
 
    // return total pairs
    return res;
}
 
// Driver program
int main()
{
    int A1[] = { 1, 1, 3, 4, 5, 6, 6 };
    int A2[] = { 1, 4, 4, 5, 7 }, K = 10;
 
    int n1 = sizeof(A1) / sizeof(A1[0]);
    int n2 = sizeof(A2) / sizeof(A2[0]);
 
    // function call to print required answer
    cout << countPairs(A1, A2, n1, n2, K);
 
    return 0;
}

// Java implementation of above approach.
import java.util.*;
class GfG {
 
// Function to return the count of pairs
// having sum equal to K
static int countPairs(int A1[], int A2[] , int n1, int n2, int K)
{
    // Initialize pairs to 0
    int res = 0;
 
    // create map of elements of array A1
    Map<Integer, Integer> m = new HashMap<Integer, Integer> ();
    for (int i = 0; i < n1; ++i)
    {
        if(m.containsKey(A1[i]))
        m.put(A1[i], m.get(A1[i]) + 1);
        else
        m.put(A1[i], 1);
    }
 
    // count total pairs
    for (int i = 0; i < n2; ++i) {
        int temp = K - A2[i];
 
        if (m.containsKey(temp) && m.get(temp) != 0) {
            res++;
 
            // Every element can be part
            // of at most one pair.
            m.put(temp, m.get(A1[i]) - 1);
        }
    }
 
    // return total pairs
    return res;
}
 
// Driver program
public static void main(String[] args)
{
    int A1[] = { 1, 1, 3, 4, 5, 6, 6 };
    int A2[] = { 1, 4, 4, 5, 7 }, K = 10;
 
    int n1 = A1.length;
    int n2 = A2.length;
 
    // function call to print required answer
    System.out.println(countPairs(A1, A2, n1, n2, K));
}
}

# Python3 implementation of above approach
 
# Function to return the count of
# pairs having sum equal to K
def countPairs(A1, A2, n1, n2, K):
     
    # Initialize pairs to 0
    res = 0
     
    # Create dictionary of elements
    # of array A1
    m = dict()
    for i in range(0, n1):
        if A1[i] not in m.keys():
            m[A1[i]] = 1
        else:
            m[A1[i]] = m[A1[i]] + 1
         
    # count total pairs
    for i in range(0, n2):
        temp = K - A2[i]
        if temp in m.keys():
            res = res + 1
             
            # Every element can be part
            # of at most one pair
            m[temp] = m[temp] - 1
     
    # return total pairs
    return res
 
# Driver Code
A1 = [1, 1, 3, 4, 5, 6 ,6]
A2 = [1, 4, 4, 5, 7]
K = 10
 
n1 = len(A1)
n2 = len(A2)
 
# function call to print required answer
print(countPairs(A1, A2, n1, n2, K))
         
# This code is contributed
# by Shashank_Sharma

// C# implementation of above approach.
using System;
using System.Collections.Generic;
 
class GfG
{
 
// Function to return the count of pairs
// having sum equal to K
static int countPairs(int []A1, int []A2 ,
                        int n1, int n2, int K)
{
    // Initialize pairs to 0
    int res = 0;
 
    // create map of elements of array A1
    Dictionary<int,int> m = new Dictionary<int,int> ();
    for (int i = 0; i < n1; ++i)
    {
        int a;
        if(m.ContainsKey(A1[i]))
        {
            a = m[A1[i]] + 1;
            m.Remove(A1[i]);
            m.Add(A1[i], a);
        }
        else
        m.Add(A1[i], 1);
    }
 
    // count total pairs
    for (int i = 0; i < n2; ++i)
    {
        int temp = K - A2[i];
 
        if (m.ContainsKey(temp) && m[temp] != 0)
        {
            res++;
 
            // Every element can be part
            // of at most one pair.
            m.Remove(temp);
            m.Add(temp, m[A1[i]] - 1);
        }
    }
 
    // return total pairs
    return res;
}
 
// Driver program
public static void Main()
{
    int []A1 = { 1, 1, 3, 4, 5, 6, 6 };
    int []A2 = { 1, 4, 4, 5, 7 };
    int K = 10;
 
    int n1 = A1.Length;
    int n2 = A2.Length;
 
    // function call to print required answer
    Console.WriteLine(countPairs(A1, A2, n1, n2, K));
}
}
 
/* This code contributed by PrinciRaj1992 */

<script>
 
// JavaScript implementation of above approach.
 
 
// Function to return the count of pairs
// having sum equal to K
function countPairs(A1, A2, n1, n2, K)
{
    // Initialize pairs to 0
    let res = 0;
 
    // create map of elements of array A1
    let m = new Map();
    for (let i = 0; i < n1; ++i){
        if(m.has(A1[i])){
            m.set(A1[i],m.get(A1[i])+1);
        }
        else m.set(A1[i],1);
    }
 
    // count total pairs
    for (let i = 0; i < n2; ++i) {
        let temp = K - A2[i];
 
        if (m.has(temp)) {
            res++;
 
            // Every element can be part
            // of at most one pair.
            m.set(temp,m.get(temp)-1);
        }
    }
 
    // return total pairs
    return res;
}
 
// Driver program
 
let A1 = [ 1, 1, 3, 4, 5, 6, 6 ];
let A2 = [ 1, 4, 4, 5, 7 ], K = 10;
 
let n1 = A1.length;
let n2 = A2.length;
 
// function call to print required answer
document.write(countPairs(A1, A2, n1, n2, K));
 
//  This code is contributed by shinjanpatra
 
</script>

4

Complejidad de tiempo: O(N+M), ya que se están ejecutando dos bucles. Uno por N veces y el otro por M veces.

Espacio Auxiliar: O(N+M)