Dada una array de n elementos distintos y positivos, la tarea es encontrar un par cuya suma ya exista en la array dada.
Ejemplos:
Input : arr[] = {2, 8, 7, 1, 5};
Output : 2 5
7 1
Input : arr[] = {7, 8, 5, 9, 11};
Output : Not Exist
Un enfoque ingenuo es ejecutar tres bucles para encontrar un par cuya suma exista en una array.
Implementación:
C++
// A simple C++ program to find pair whose sum
// already exists in array
#include <bits/stdc++.h>
using namespace std;
// Function to find pair whose sum exists in arr[]
void findPair(int arr[], int n)
{
bool found = false;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = 0; k < n; k++) {
if (arr[i] + arr[j] == arr[k]) {
cout << arr[i] << " " << arr[j] << endl;
found = true;
}
}
}
}
if (found == false)
cout << "Not exist" << endl;
}
// Driven code
int main()
{
int arr[] = { 10, 4, 8, 13, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
findPair(arr, n);
return 0;
}
Java
// A simple Java program to find
// pair whose sum already exists
// in array
import java.io.*;
public class GFG {
// Function to find pair whose
// sum exists in arr[]
static void findPair(int[] arr, int n)
{
boolean found = false;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = 0; k < n; k++) {
if (arr[i] + arr[j] == arr[k]) {
System.out.println(arr[i] +
" " + arr[j]);
found = true;
}
}
}
}
if (found == false)
System.out.println("Not exist");
}
// Driver code
static public void main(String[] args)
{
int[] arr = {10, 4, 8, 13, 5};
int n = arr.length;
findPair(arr, n);
}
}
// This code is contributed by vt_m.
Python3
# A simple python program to find pair
# whose sum already exists in array
# Function to find pair whose sum
# exists in arr[]
def findPair(arr, n):
found = False
for i in range(0, n):
for j in range(i + 1, n):
for k in range(0, n):
if (arr[i] + arr[j] == arr[k]):
print(arr[i], arr[j])
found = True
if (found == False):
print("Not exist")
# Driver code
if __name__ == '__main__':
arr = [ 10, 4, 8, 13, 5 ]
n = len(arr)
findPair(arr, n)
# This code contributed by 29AjayKumar
C#
// A simple C# program to find
// pair whose sum already exists
// in array
using System;
public class GFG {
// Function to find pair whose
// sum exists in arr[]
static void findPair(int[] arr, int n)
{
bool found = false;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = 0; k < n; k++) {
if (arr[i] + arr[j] == arr[k]) {
Console.WriteLine(arr[i] +
" " + arr[j]);
found = true;
}
}
}
}
if (found == false)
Console.WriteLine("Not exist");
}
// Driver code
static public void Main(String []args)
{
int[] arr = {10, 4, 8, 13, 5};
int n = arr.Length;
findPair(arr, n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// A simple php program to
// find pair whose sum
// already exists in array
// Function to find pair whose
// sum exists in arr[]
function findPair($arr, $n)
{
$found = false;
for ($i = 0; $i < $n; $i++)
{
for ($j = $i + 1; $j < $n; $j++)
{
for ($k = 0; $k < $n; $k++)
{
if ($arr[$i] + $arr[$j] == $arr[$k])
{
echo $arr[$i] , " " , $arr[$j] ;
$found = true;
}
}
}
}
if ($found == false)
echo "Not exist" ;
}
// Driver code
$arr = array( 10, 4, 8, 13, 5 );
$n = sizeof($arr) / sizeof($arr[0]);
findPair($arr, $n);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// A simple Javascript program to find
// pair whose sum already exists
// in array
// Function to find pair whose
// sum exists in arr[]
function findPair(arr,n)
{
let found = false;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = 0; k < n; k++) {
if (arr[i] + arr[j] == arr[k]) {
document.write(arr[i] +
" " + arr[j]+"<br>");
found = true;
}
}
}
}
if (found == false)
document.write("Not exist");
}
// Driver code
let arr=[10, 4, 8, 13, 5];
let n = arr.length;
findPair(arr, n);
// This code is contributed by patel2127
</script>
Producción
8 5
Complejidad temporal: O(n 3 )
Espacio auxiliar: O(1)
Una solución eficiente es almacenar todos los elementos en una tabla hash ( unordered_set en C++ ) y verificar uno por uno todos los pares y verificar que su suma exista en el conjunto o no. Si existe en el conjunto, imprima el par. Si no se encuentra ningún par en la array, la impresión no existe.
Implementación:
C++
// C++ program to find pair whose sum already
// exists in array
#include <bits/stdc++.h>
using namespace std;
// Function to find pair whose sum exists in arr[]
void findPair(int arr[], int n)
{
// Hash to store all element of array
unordered_set<int> s;
for (int i = 0; i < n; i++)
s.insert(arr[i]);
bool found = false;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Check sum already exists or not
if (s.find(arr[i] + arr[j]) != s.end()) {
cout << arr[i] << " " << arr[j] << endl;
found = true;
}
}
}
if (found == false)
cout << "Not exist" << endl;
}
// Driven code
int main()
{
int arr[] = { 10, 4, 8, 13, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
findPair(arr, n);
return 0;
}
Java
// Java program to find pair whose sum
// already exists in array
import java.util.*;
import java.lang.*;
import java.io.*;
class Getpairs {
// Function to find pair whose sum
// exists in arr[]
public static void findPair(int[] arr, int n)
{
/* store all the array elements as a
Hash value*/
HashSet<Integer> s = new HashSet<Integer>();
for (Integer i : arr) {
s.add(i);
}
/* Run two loop and check for the sum
in the Hashset*/
/* if not a single pair exist then found
will be false else true*/
boolean found = false;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int sum = arr[i] + arr[j];
if (s.contains(sum)) {
/* if the sum is present in
hashset then found become
true*/
found = true;
System.out.println(arr[i] + " "
+ arr[j]);
}
}
}
if (found == false)
System.out.println("Not Exist ");
}
// driver function
public static void main(String args[])
{
int[] arr = { 10, 4, 8, 13, 5 };
int n = arr.length;
findPair(arr, n);
}
}
// This code is contributed by Smarak Chopdar
Python3
# Python3 program to find pair whose
# sum already exist in array
# Function to find pair whose
# sum exists in arr[]
def findPair(arr, n):
# hash to store all element of array
s = {i : 1 for i in arr}
found = False
for i in range(n):
for j in range(i + 1, n):
# check if sum already exists or not
if arr[i] + arr[j] in s.keys():
print(arr[i], arr[j])
found = True
if found == False:
print("Not exist")
# Driver code
arr = [10, 4, 8, 13, 5]
n = len(arr)
findPair(arr, n)
# This code is contributed
# by Mohit Kumar
C#
// C# program to find pair whose sum
// already exists in array
using System;
using System.Collections.Generic;
class Getpairs
{
// Function to find pair whose sum
// exists in arr[]
public static void findPair(int[] arr, int n)
{
/* store all the array elements as a
Hash value*/
HashSet<int> s = new HashSet<int>();
foreach (int i in arr)
{
s.Add(i);
}
/* Run two loop and check for the sum
in the Hashset*/
/* if not a single pair exist then found
will be false else true*/
bool found = false;
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
int sum = arr[i] + arr[j];
if (s.Contains(sum))
{
/* if the sum is present in
hashset then found become
true*/
found = true;
Console.WriteLine(arr[i] + " "
+ arr[j]);
}
}
}
if (found == false)
Console.WriteLine("Not Exist ");
}
// Driver code
public static void Main()
{
int[] arr = { 10, 4, 8, 13, 5 };
int n = arr.Length;
findPair(arr, n);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find pair whose sum
// already exists in array
// Function to find pair whose sum
// exists in arr[]
function findPair(arr,n)
{
/* store all the array elements as a
Hash value*/
let s = new Set();
for (let i=0;i<arr.length;i++) {
s.add(arr[i]);
}
/* Run two loop and check for the sum
in the Hashset*/
/* if not a single pair exist then found
will be false else true*/
let found = false;
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
let sum = arr[i] + arr[j];
if (s.has(sum)) {
/* if the sum is present in
hashset then found become
true*/
found = true;
document.write(arr[i] + " "
+ arr[j]+"<br>");
}
}
}
if (found == false)
document.write("Not Exist ");
}
// driver function
let arr=[10, 4, 8, 13, 5 ];
let n = arr.length;
findPair(arr, n);
// This code is contributed by unknown2108
</script>
Producción
8 5
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(n 2 )
Este artículo es una contribución de DANISH_RAZA . 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.
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