Dadas tres arrays ordenadas de enteros A[] , B[] y C[] , la tarea es encontrar tres enteros, uno de cada array, de modo que sumen un valor objetivo dado X . Escriba Sí o No dependiendo de si existe o no dicho triplete.
Ejemplos:
Entrada: A[] = {2}, B[] = {1, 6, 7}, C[] = {4, 5}, X = 12
Salida: Sí
A[0] + B[1] + C[ 0] = 2 + 6 + 4 = 12
Entrada: A[] = {2}, B[] = {1, 6, 7}, C[] = {4, 5}, X = 14
Salida: Sí
A[ 0] + B[2] + C[1] = 2 + 7 + 5 = 14
Enfoque: Ya hemos discutido un enfoque basado en hash en este artículo que ocupa O (N) espacio adicional.
En este artículo, resolveremos este problema utilizando un método de uso eficiente del espacio que ocupa O(1) espacio adicional. La idea es utilizar la técnica de dos punteros.
Recorreremos el más pequeño de todos los arreglos y para cada índice i , usaremos dos punteros en los dos arreglos más grandes para encontrar un par con una suma igual a X – A[i] (asumiendo que A[] es el más pequeño en longitud entre las tres rryas).
Ahora, ¿cuál es la idea detrás de usar dos punteros en dos arreglos más grandes? Intentaremos entender lo mismo a partir de un ejemplo.
Supongamos que
len(A) = 100000
len(B) = 10000
len(C) = 10
Caso 1: aplicar dos punteros en dos arrays más grandes
El número de iteraciones será del orden = len(C) * (len(A) + len (B)) = 10 * (110000) = 1100000
Caso 2: Aplicar dos punteros en dos arrays más pequeñas
El número de iteraciones será del orden = len(A) * (len(B) + len(C)) = 100000 * ( 10010) = 1001000000
Caso 3: Aplicar dos punteros en la array más pequeña y más grande
El número de iteraciones será del orden = len(B) * (len(A) + len(C)) = 10000 * (100000 + 10) = 1000100000
As Como podemos ver, el Caso 1 es el más óptimo para este ejemplo y se puede demostrar fácilmente que también es el más óptimo en general.
Algoritmo:
- Ordene las arrays en orden creciente de sus longitudes.
- Digamos que la array más pequeña después de ordenar es A[]. Luego, itere a través de todos los elementos de A[] y para cada índice ‘i’, aplique dos punteros en las otras dos arrays. Pondremos un puntero al comienzo de la array B[] y un puntero al final de la array C[]. Llamemos al puntero ‘j’ y ‘k’ respectivamente.
- Si B[j] + C[k] = X – A[i], encontramos una coincidencia.
- Si B[j] + C[k] es menor que X – A[i], aumentamos el valor de ‘j’ en 1.
- Si B[j] + C[k] es mayor que X – A[i], disminuimos el valor de ‘k’ en 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns true if there
// exists a triplet with sum x
bool existsTriplet(int a[], int b[],
int c[], int x, int l1,
int l2, int l3)
{
// Sorting arrays such that a[]
// represents smallest array
if (l2 <= l1 and l2 <= l3)
swap(l2, l1), swap(a, b);
else if (l3 <= l1 and l3 <= l2)
swap(l3, l1), swap(a, c);
// Iterating the smallest array
for (int i = 0; i < l1; i++) {
// Two pointers on second and third array
int j = 0, k = l3 - 1;
while (j < l2 and k >= 0) {
// If a valid triplet is found
if (a[i] + b[j] + c[k] == x)
return true;
if (a[i] + b[j] + c[k] < x)
j++;
else
k--;
}
}
return false;
}
// Driver code
int main()
{
int a[] = { 2, 7, 8, 10, 15 };
int b[] = { 1, 6, 7, 8 };
int c[] = { 4, 5, 5 };
int l1 = sizeof(a) / sizeof(int);
int l2 = sizeof(b) / sizeof(int);
int l3 = sizeof(c) / sizeof(int);
int x = 14;
if (existsTriplet(a, b, c, x, l1, l2, l3))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function that returns true if there
// exists a triplet with sum x
static boolean existsTriplet(int a[], int b[],
int c[], int x, int l1,
int l2, int l3)
{
// Sorting arrays such that a[]
// represents smallest array
if (l2 <= l1 && l2 <= l3)
{
swap(l2, l1);
swap(a, b);
}
else if (l3 <= l1 && l3 <= l2)
{
swap(l3, l1);
swap(a, c);
}
// Iterating the smallest array
for (int i = 0; i < l1; i++)
{
// Two pointers on second and third array
int j = 0, k = l3 - 1;
while (j < l2 && k >= 0)
{
// If a valid triplet is found
if (a[i] + b[j] + c[k] == x)
return true;
if (a[i] + b[j] + c[k] < x)
j++;
else
k--;
}
}
return false;
}
private static void swap(int x, int y)
{
int temp = x;
x = y;
y = temp;
}
private static void swap(int []x, int []y)
{
int []temp = x;
x = y;
y = temp;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 2, 7, 8, 10, 15 };
int b[] = { 1, 6, 7, 8 };
int c[] = { 4, 5, 5 };
int l1 = a.length;
int l2 = b.length;
int l3 = c.length;
int x = 14;
if (existsTriplet(a, b, c, x, l1, l2, l3))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Rajput-Ji
Python3
# Function that returns True if there
# exists a triplet with sum x
def existsTriplet(a, b,c, x, l1,l2, l3):
# Sorting arrays such that a
# represents smallest array
if (l2 <= l1 and l2 <= l3):
l1, l2 = l2,l1
a, b = b,a
elif (l3 <= l1 and l3 <= l2):
l1, l3 = l3,l1
a, c = c,a
# Iterating the smallest array
for i in range(l1):
# Two pointers on second and third array
j = 0
k = l3 - 1
while (j < l2 and k >= 0):
# If a valid triplet is found
if (a[i] + b[j] + c[k] == x):
return True
if (a[i] + b[j] + c[k] < x):
j += 1
else:
k -= 1
return False
# Driver code
a = [ 2, 7, 8, 10, 15 ]
b = [ 1, 6, 7, 8 ]
c = [ 4, 5, 5 ]
l1 = len(a)
l2 = len(b)
l3 = len(c)
x = 14
if (existsTriplet(a, b, c, x, l1, l2, l3)):
print("Yes")
else:
print("No")
# This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
// Function that returns true if there
// exists a triplet with sum x
static bool existsTriplet(int []a, int []b,
int []c, int x, int l1,
int l2, int l3)
{
// Sorting arrays such that a[]
// represents smallest array
if (l2 <= l1 && l2 <= l3)
{
swap(l2, l1);
swap(a, b);
}
else if (l3 <= l1 && l3 <= l2)
{
swap(l3, l1);
swap(a, c);
}
// Iterating the smallest array
for (int i = 0; i < l1; i++)
{
// Two pointers on second and third array
int j = 0, k = l3 - 1;
while (j < l2 && k >= 0)
{
// If a valid triplet is found
if (a[i] + b[j] + c[k] == x)
return true;
if (a[i] + b[j] + c[k] < x)
j++;
else
k--;
}
}
return false;
}
private static void swap(int x, int y)
{
int temp = x;
x = y;
y = temp;
}
private static void swap(int []x, int []y)
{
int []temp = x;
x = y;
y = temp;
}
// Driver code
public static void Main(String[] args)
{
int []a = { 2, 7, 8, 10, 15 };
int []b = { 1, 6, 7, 8 };
int []c = { 4, 5, 5 };
int l1 = a.Length;
int l2 = b.Length;
int l3 = c.Length;
int x = 14;
if (existsTriplet(a, b, c, x, l1, l2, l3))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
// Function that returns true if there
// exists a triplet with sum x
function existsTriplet(a, b, c, x, l1,
l2, l3)
{
// Sorting arrays such that a[]
// represents smallest array
if (l2 <= l1 && l2 <= l3)
{
temp = l1; l1 = l2; l2 = temp;
temp = a; a = b; b = temp;
}
else if (l3 <= l1 && l3 <= l2)
{
temp = l1; l1 = l3; l3 = temp;
temp = a; a = c; c = temp;
}
// Iterating the smallest array
for (var i = 0; i < l1; i++) {
// Two pointers on second and third array
var j = 0, k = l3 - 1;
while (j < l2 && k >= 0) {
// If a valid triplet is found
if (a[i] + b[j] + c[k] == x)
return true;
if (a[i] + b[j] + c[k] < x)
j++;
else
k--;
}
}
return false;
}
// Driver code
var a = [ 2, 7, 8, 10, 15 ];
var b = [ 1, 6, 7, 8 ];
var c = [ 4, 5, 5 ];
var l1 = a.length;
var l2 = b.length;
var l3 = c.length;
var x = 14;
if (existsTriplet(a, b, c, x, l1, l2, l3))
document.write("Yes");
else
document.write("No");
</script>
Yes
Complejidad del tiempo: O(min(len(A), len(B), len(C)) * max(len(A), len(B), len(C)))
Espacio auxiliar : O(1), desde no se ha ocupado ningún espacio extra.
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA