Dada una array de números enteros, debe encontrar tres números tales que la suma de dos elementos sea igual al tercer elemento.
Ejemplos:
Input : {5, 32, 1, 7, 10, 50, 19, 21, 2}
Output : 21, 2, 19
Input : {5, 32, 1, 7, 10, 50, 19, 21, 0}
Output : no such triplet exist
Fuente de la pregunta: experiencia de entrevista con Arcesium | Conjunto 7 (En el campus para prácticas)
Enfoque simple: ejecute tres bucles y verifique si existe un triplete tal que la suma de dos elementos sea igual al tercer elemento.
Complejidad del tiempo: O(n^3)
Enfoque eficiente: la idea es similar a encontrar un triplete que sume un valor dado.
- Primero ordene la array dada.
- Comience a fijar el mayor elemento de tres desde atrás y recorra la array para encontrar los otros dos números que suman el tercer elemento.
- Tome dos punteros j (desde el frente) y k (inicialmente i-1) para encontrar el menor de los dos números y desde i-1 para encontrar el mayor de los dos números restantes
- Si la suma de ambos números sigue siendo menor que A[i], entonces necesitamos aumentar el valor de la suma de dos números, aumentando así el puntero j, para aumentar el valor de A[j] + A[ k] .
- Si la suma de ambos números es mayor que A[i], entonces debemos disminuir el valor de la suma de dos números, por lo tanto, disminuir el puntero k para disminuir el valor total de A[j] + A[k ] .
La imagen de abajo es una ejecución en seco del enfoque anterior:
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find three numbers
// such that sum of two makes the
// third element in array
#include <bits/stdc++.h>
using namespace std;
// Utility function for finding
// triplet in array
void findTriplet(int arr[], int n)
{
// sort the array
sort(arr, arr + n);
// for every element in arr
// check if a pair exist(in array) whose
// sum is equal to arr element
for (int i = n - 1; i >= 0; i--) {
int j = 0;
int k = i - 1;
// Iterate forward and backward to find
// the other two elements
while (j < k) {
// If the two elements sum is
// equal to the third element
if (arr[i] == arr[j] + arr[k]) {
// pair found
cout << "numbers are " << arr[i] << " "
<< arr[j] << " " << arr[k] << endl;
return;
}
// If the element is greater than
// sum of both the elements, then try
// adding a smaller number to reach the
// equality
else if (arr[i] > arr[j] + arr[k])
j += 1;
// If the element is smaller, then
// try with a smaller number
// to reach equality, so decrease K
else
k -= 1;
}
}
// No such triplet is found in array
cout << "No such triplet exists";
}
// driver program
int main()
{
int arr[] = { 5, 32, 1, 7, 10, 50, 19, 21, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
findTriplet(arr, n);
return 0;
}
Java
// Java program to find three numbers
// such that sum of two makes the
// third element in array
import java.util.Arrays;
public class GFG {
// utility function for finding
// triplet in array
static void findTriplet(int arr[], int n)
{
// sort the array
Arrays.sort(arr);
// for every element in arr
// check if a pair exist(in array) whose
// sum is equal to arr element
for (int i = n - 1; i >= 0; i--) {
int j = 0;
int k = i - 1;
while (j < k) {
if (arr[i] == arr[j] + arr[k]) {
// pair found
System.out.println("numbers are " + arr[i] + " "
+ arr[j] + " " + arr[k]);
return;
}
else if (arr[i] > arr[j] + arr[k])
j += 1;
else
k -= 1;
}
}
// no such triplet is found in array
System.out.println("No such triplet exists");
}
// driver program
public static void main(String args[])
{
int arr[] = { 5, 32, 1, 7, 10, 50, 19, 21, 2 };
int n = arr.length;
findTriplet(arr, n);
}
}
// This code is contributed by Sumit Ghosh
Python
# Python program to find three numbers # such that sum of two makes the # third element in array # utility function for finding # triplet in array def findTriplet(arr, n): # sort the array arr.sort() # for every element in arr # check if a pair exist(in array) whose # sum is equal to arr element i = n - 1 while(i >= 0): j = 0 k = i - 1 while (j < k): if (arr[i] == arr[j] + arr[k]): # pair found print "numbers are ", arr[i], arr[j], arr[k] return elif (arr[i] > arr[j] + arr[k]): j += 1 else: k -= 1 i -= 1 # no such triplet is found in array print "No such triplet exists" # driver program arr = [ 5, 32, 1, 7, 10, 50, 19, 21, 2 ] n = len(arr) findTriplet(arr, n) # This code is contributed by Sachin Bisht
C#
// C# program to find three numbers
// such that sum of two makes the
// third element in array
using System;
public class GFG {
// utility function for finding
// triplet in array
static void findTriplet(int[] arr, int n)
{
// sort the array
Array.Sort(arr);
// for every element in arr
// check if a pair exist(in
// array) whose sum is equal
// to arr element
for (int i = n - 1; i >= 0; i--) {
int j = 0;
int k = i - 1;
while (j < k) {
if (arr[i] == arr[j] + arr[k]) {
// pair found
Console.WriteLine("numbers are "
+ arr[i] + " " + arr[j]
+ " " + arr[k]);
return;
}
else if (arr[i] > arr[j] + arr[k])
j += 1;
else
k -= 1;
}
}
// no such triplet is found in array
Console.WriteLine("No such triplet exists");
}
// driver program
public static void Main()
{
int[] arr = { 5, 32, 1, 7, 10, 50,
19, 21, 2 };
int n = arr.Length;
findTriplet(arr, n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find three
// numbers such that sum of
// two makes the third
// element in array
// utility function for
// finding triplet in array
function findTriplet($arr, $n)
{
// sort the array
sort($arr);
// for every element in
// arr check if a pair
// exist(in array) whose
// sum is equal to arr element
for ($i = $n - 1; $i >= 0; $i--)
{
$j = 0;
$k = $i - 1;
while ($j < $k)
{
if ($arr[$i] == $arr[$j] + $arr[$k])
{
// pair found
echo "numbers are ", $arr[$i], " ",
$arr[$j], " ",
$arr[$k];
return;
}
else if ($arr[$i] > $arr[$j] +
$arr[$k])
$j += 1;
else
$k -= 1;
}
}
// no such triplet
// is found in array
echo "No such triplet exists";
}
// Driver Code
$arr = array(5, 32, 1, 7, 10,
50, 19, 21, 2 );
$n = count($arr);
findTriplet($arr, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find three numbers
// such that sum of two makes the
// third element in array
// Utility function for finding
// triplet in array
function findTriplet(arr, n)
{
// sort the array
arr.sort((a,b) => a-b);
// for every element in arr
// check if a pair exist(in array) whose
// sum is equal to arr element
for (let i = n - 1; i >= 0; i--) {
let j = 0;
let k = i - 1;
// Iterate forward and backward to find
// the other two elements
while (j < k) {
// If the two elements sum is
// equal to the third element
if (arr[i] == arr[j] + arr[k]) {
// pair found
document.write("numbers are " + arr[i] +
" " + arr[j] + " " + arr[k] + "<br>");
return;
}
// If the element is greater than
// sum of both the elements, then try
// adding a smaller number to reach the
// equality
else if (arr[i] > arr[j] + arr[k])
j += 1;
// If the element is smaller, then
// try with a smaller number
// to reach equality, so decrease K
else
k -= 1;
}
}
// No such triplet is found in array
document.write("No such triplet exists");
}
// driver program
let arr = [ 5, 32, 1, 7, 10, 50, 19, 21, 2 ];
let n = arr.length;
findTriplet(arr, n);
// This code is contributed by Mayank Tyagi
</script>
Producción
numbers are 21 2 19
Complejidad del tiempo: O(N^2)
Otro enfoque: la idea es similar al enfoque anterior:
- Ordenar la array dada.
- Inicie un bucle anidado, fijando el primer elemento i (de 0 a n-1) y moviendo el otro j (de i+1 a n-1).
- Tome la suma de ambos elementos y búsquelo en la array restante usando la búsqueda binaria.
Implementación:
C++
// CPP program to find three numbers
// such that sum of two makes the
// third element in array
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// function to perform binary search
bool search(int sum, int start, int end, int arr[])
{
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == sum) {
return true;
}
else if (arr[mid] > sum) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
return false;
}
// function to find the triplets
void findTriplet(int arr[], int n)
{
// sorting the array
sort(arr, arr + n);
// initialising nested loops
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// finding the sum of the numbers
if (search((arr[i] + arr[j]), j, n - 1, arr)) {
// printing out the first triplet
cout << "Numbers are: " << arr[i] << " "
<< arr[j] << " " << (arr[i] + arr[j]);
return;
}
}
}
// if no such triplets are found
cout << "No such numbers exist" << endl;
}
int main()
{
int arr[] = { 5, 32, 1, 7, 10, 50, 19, 21, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
findTriplet(arr, n);
return 0;
}
// This code is contributed by Sarthak Delori
Java
// Java program to find three numbers
// such that sum of two makes the
// third element in array
import java.util.*;
class GFG{
// Function to perform binary search
static boolean search(int sum, int start,
int end, int arr[])
{
while (start <= end)
{
int mid = (start + end) / 2;
if (arr[mid] == sum)
{
return true;
}
else if (arr[mid] > sum)
{
end = mid - 1;
}
else
{
start = mid + 1;
}
}
return false;
}
// Function to find the triplets
static void findTriplet(int arr[], int n)
{
// Sorting the array
Arrays.sort(arr);
// Initialising nested loops
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// Finding the sum of the numbers
if (search((arr[i] + arr[j]), j, n - 1, arr))
{
// Printing out the first triplet
System.out.print("Numbers are: " + arr[i] + " " +
arr[j] + " " + (arr[i] + arr[j]));
return;
}
}
}
// If no such triplets are found
System.out.print("No such numbers exist");
}
// Driver code
public static void main(String args[])
{
int arr[] = { 5, 32, 1, 7, 10, 50, 19, 21, 2 };
int n = arr.length;
findTriplet(arr, n);
}
}
// This code is contributed by target_2
Python3
# Python program to find three numbers
# such that sum of two makes the
# third element in array
from functools import cmp_to_key
def mycmp(a, b):
return a - b
def search(sum, start, end, arr):
while (start <= end):
mid = (start + end) // 2
if (arr[mid] == sum):
return True
elif (arr[mid] > sum):
end = mid - 1
else:
start = mid + 1
return False
# Utility function for finding
# triplet in array
def findTriplet(arr, n):
# sort the array
arr.sort(key = cmp_to_key(mycmp))
# initialising nested loops
for i in range(n):
for j in range(i + 1,n):
if (search((arr[i] + arr[j]), j, n - 1, arr)):
print(f"numbers are {arr[i]} {arr[j]} {( arr[i] + arr[j] )}")
return
# No such triplet is found in array
print("No such triplet exists")
# driver program
arr = [ 5, 32, 1, 7, 10, 50, 19, 21, 2 ]
n = len(arr)
findTriplet(arr, n)
# This code is contributed by shinjanpatra
C#
// C# program to find three numbers
// such that sum of two makes the
// third element in array
using System;
public class GFG {
// function to perform binary search
static bool search(int sum, int start, int end, int [] arr)
{
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == sum) {
return true;
}
else if (arr[mid] > sum) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
return false;
}
// utility function for finding
// triplet in array
static void findTriplet(int[] arr, int n)
{
// sort the array
Array.Sort(arr);
// for every element in arr
// check if a pair exist(in
// array) whose sum is equal
// to arr element
for (int i = 0; i < n; i++) {
for(int j=i+1;j<n;j++)
{
// finding the sum of the numbers
if (search((arr[i] + arr[j]), j, n - 1, arr)) {
// pair found
Console.WriteLine("Numbers are "
+ arr[i] + " " + arr[j]
+ " " + (arr[i]+arr[j]));
return;
}
}
}
// no such triplet is found in array
Console.WriteLine("No such triplet exists");
}
// driver program
public static void Main()
{
int[] arr = { 5, 32, 1, 7, 10, 50,
19, 21, 2 };
int n = arr.Length;
findTriplet(arr, n);
}
}
// This code is contributed by Aarti_Rathi
Javascript
<script>
// Javascript program to find three numbers
// such that sum of two makes the
// third element in array
bool search(sum, start, end, arr)
{
while (start <= end) {
let mid = (start + end) / 2;
if (arr[mid] == sum) {
return true;
}
else if (arr[mid] > sum) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
return false;
}
// Utility function for finding
// triplet in array
function findTriplet(arr, n)
{
// sort the array
arr.sort((a,b) => a-b);
// initialising nested loops
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (search((arr[i] + arr[j]), j, n - 1, arr)) {
document.write("numbers are " + arr[i] +
" " + arr[j] + " " + ( arr[i] + arr[j] ) + "<br>");
}
}
}
// No such triplet is found in array
document.write("No such triplet exists");
}
// driver program
let arr = [ 5, 32, 1, 7, 10, 50, 19, 21, 2 ];
let n = arr.length;
findTriplet(arr, n);
// This code is contributed by Sarthak Delori
</script>
Producción
Numbers are: 2 5 7
Complejidad de tiempo: O(N^2*log N)
Complejidad de espacio: O(1)
Este artículo es una contribución de Mandeep Singh . 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