Dadas dos arrays de enteros donde el tamaño máximo de la primera array es grande y el de la segunda array es pequeño. Tu tarea es encontrar si hay un par en la primera array cuya suma está presente en la segunda array.
Ejemplos:
Input: 4 1 5 10 8 3 2 20 13 Output: 1
Enfoque: Tenemos x + y = z. Esto se puede reescribir como x = z – y. Esto significa que necesitamos encontrar un elemento x en el arreglo 1 tal que sea el resultado de z (segundo arreglo) – y (primer arreglo). Para esto, use hashing para realizar un seguimiento de dicho elemento x.
C++
// C++ code for finding required pairs
#include <bits/stdc++.h>
using namespace std;
// The function to check if beautiful pair exists
bool pairExists(int arr1[], int m, int arr2[], int n)
{
// Set for hashing
unordered_set<int> s;
// Traversing the first array
for (int i = 0; i < m; i++) {
// Traversing the second array to check for
// every j corresponding to single i
for (int j = 0; j < n; j++) {
// x + y = z => x = y - z
if (s.find(arr2[j] - arr1[i]) != s.end())
// if such x exists then we return true
return true;
}
// hash to make use of it next time
s.insert(arr1[i]);
}
// no pair exists
return false;
}
// Driver Code
int main()
{
int arr1[] = { 1, 5, 10, 8 };
int arr2[] = { 2, 20, 13 };
// If pair exists then 1 else 0
// 2nd argument as size of first array
// fourth argument as sizeof 2nd array
if (pairExists(arr1, 4, arr2, 3))
cout << 1 << endl;
else
cout << 0 << endl;
return 0;
}
Java
// Java code for finding required pairs
import java.util.*;
class GFG
{
// The function to check if beautiful pair exists
static boolean pairExists(int []arr1, int m, int []arr2, int n)
{
// Set for hashing
Set<Integer> s =new HashSet<Integer>();
// Traversing the first array
for (int i = 0; i < m; i++) {
// Traversing the second array to check for
// every j corresponding to single i
for (int j = 0; j < n; j++)
{
// x + y = z => x = y - z
if (s.contains(arr2[j] - arr1[i]))
// if such x exists then we return true
return true;
}
// hash to make use of it next time
s.add(arr1[i]);
}
// no pair exists
return false;
}
// Driver Code
public static void main(String []args)
{
int []arr1 = { 1, 5, 10, 8 };
int []arr2 = { 2, 20, 13 };
// If pair exists then 1 else 0
// 2nd argument as size of first array
// fourth argument as sizeof 2nd array
if (pairExists(arr1, 4, arr2, 3))
System.out.println(1);
else
System.out.println(0);
}
// This code is contributed by ihritik
}
Python3
# Python3 code for finding required pairs from typing import List # The function to check if beautiful pair exists def pairExists(arr1: List[int], m: int, arr2: List[int], n: int) -> bool: # Set for hashing s = set() # Traversing the first array for i in range(m): # Traversing the second array to check for # every j corresponding to single i for j in range(n): # x + y = z => x = y - z if (arr2[2] - arr1[2]) not in s: # If such x exists then we # return true return True # Hash to make use of it next time s.add(arr1[i]) # No pair exists return False # Driver Code if __name__ == "__main__": arr1 = [ 1, 5, 10, 8 ] arr2 = [ 2, 20, 13 ] # If pair exists then 1 else 0 # 2nd argument as size of first array # fourth argument as sizeof 2nd array if (pairExists(arr1, 4, arr2, 3)): print(1) else: print(0) # This code is contributed by sanjeev2552
C#
// C# code for finding required pairs
using System;
using System.Collections.Generic;
class GFG
{
// The function to check if
// beautiful pair exists
static bool pairExists(int []arr1,
int m, int []arr2, int n)
{
// Set for hashing
HashSet<int> s = new HashSet<int>();
// Traversing the first array
for (int i = 0; i < m; i++)
{
// Traversing the second array to check for
// every j corresponding to single i
for (int j = 0; j < n; j++)
{
// x + y = z => x = y - z
if (s.Contains(arr2[j] - arr1[i]))
// if such x exists then we return true
return true;
}
// hash to make use of it next time
s.Add(arr1[i]);
}
// no pair exists
return false;
}
// Driver Code
public static void Main()
{
int []arr1 = { 1, 5, 10, 8 };
int []arr2 = { 2, 20, 13 };
// If pair exists then 1 else 0
// 2nd argument as size of first array
// fourth argument as sizeof 2nd array
if (pairExists(arr1, 4, arr2, 3))
Console.WriteLine(1);
else
Console.WriteLine(0);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript code for finding required pairs
// The function to check if beautiful pair exists
function pairExists(arr1, m, arr2, n) {
// Set for hashing
let s = new Set();
// Traversing the first array
for (let i = 0; i < m; i++) {
// Traversing the second array to check for
// every j corresponding to single i
for (let j = 0; j < n; j++) {
// x + y = z => x = y - z
if (s.has(arr2[j] - arr1[i]))
// if such x exists then we return true
return true;
}
// hash to make use of it next time
s.add(arr1[i]);
}
// no pair exists
return false;
}
// Driver Code
let arr1 = [1, 5, 10, 8];
let arr2 = [2, 20, 13];
// If pair exists then 1 else 0
// 2nd argument as size of first array
// fourth argument as sizeof 2nd array
if (pairExists(arr1, 4, arr2, 3))
document.write(1 + "<br>");
else
document.write(0 + "<br>");
</script>
Producción:
1
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA