Dada una array arr[] que consiste en N enteros y un entero K , la tarea es imprimir todos los posibles cuatrillizos únicos (arr[i], arr[j], arr[k], arr[l]) cuya suma es K tal que todos sus índices son distintos.
Ejemplos:
Entrada: arr[] = {1, 0, -1, 0, -2, 2}, K = 0
Salida:
-2 -1 1 2
-2 0 0 0 2
-1 0 0 1
Explicación:
A continuación se muestran los cuatrillizos cuyos la suma es K (= 0):
- {-2, -1, 1, 2}
- {-2, 0, 0, 2}
- {-1, 0, 0, 1}
Entrada: arr[] = {1, 2, 3, -1}, objetivo = 5
Salida:
1 2 3 -1
Enfoque ingenuo: el enfoque más simple es generar todos los cuatrillizos posibles a partir de la array dada arr[] y si la suma de los elementos de los cuatrillizos es K , entonces inserte los cuatrillizos actuales en el HashSet para evitar el conteo de cuatrillizos duplicados. Después de verificar todos los cuatrillizos, imprima todos los cuatrillizos almacenados en el HashSet.
Complejidad de Tiempo: O(N 4 )
Espacio Auxiliar: O(N 4 )
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando la idea de generar todos los pares posibles de la array dada . Siga los pasos dados para resolver el problema:
- Inicialice un HashMap , digamos que almacena todos los cuatrillizos posibles .
- Inicialice un HashMap , digamos M que almacene la suma de todos los pares posibles de la array dada con sus índices correspondientes.
- Genere todos los pares posibles de la array dada y almacene la suma de todos los pares de elementos (arr[i], arr[j]) con sus índices (i , j) en el HashMap M.
- Ahora, genere todos los pares posibles de la array dada nuevamente y para cada suma de todos los pares de elementos (arr[i], arr[j]) si el valor (K – sum) existe en el HashMap M , luego almacene los cuatrillizos actuales en el HashMap ans .
- Después de completar los pasos anteriores, imprima todos los cuatrillizos almacenados en HashMap ans .
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
public class GFG {
// Stores the pair of indices
static class Pair {
int index1;
int index2;
// Constructor
Pair(int x, int y)
{
index1 = x;
index2 = y;
}
}
// Function to find the all the
// unique quadruplets with the
// elements at different indices
public static void
GetQuadruplets(ArrayList<Integer> nums,
int target)
{
// Stores the sum mapped to
// a List Of Pair<i, j>
HashMap<Integer, ArrayList<Pair> > map
= new HashMap<>();
// Generate all possible pairs
// for the HashMap
for (int i = 0;
i < nums.size() - 1; i++) {
for (int j = i + 1;
j < nums.size(); j++) {
// Find the sum of pairs
// of elements
int sum = nums.get(i)
+ nums.get(j);
// If the sum doesn't
// exists then update
// with the new pairs
if (!map.containsKey(sum)) {
ArrayList<Pair> temp
= new ArrayList<>();
Pair p = new Pair(i, j);
temp.add(p);
// Update the hashmap
map.put(sum, temp);
}
// Otherwise, push the new
// pair of indices to the
// current sum
else {
ArrayList<Pair> temp
= map.get(sum);
Pair p = new Pair(i, j);
temp.add(p);
// Update the hashmap
map.put(sum, temp);
}
}
}
// Stores all the Quadruplets
HashSet<ArrayList<Integer> > ans
= new HashSet<ArrayList<Integer> >();
for (int i = 0;
i < nums.size() - 1; i++) {
for (int j = i + 1;
j < nums.size(); j++) {
int lookUp = target
- (nums.get(i)
+ nums.get(j));
// If the sum with value
// (K - sum) exists
if (map.containsKey(lookUp)) {
// Get the pair of
// indices of sum
ArrayList<Pair> temp
= map.get(lookUp);
for (Pair pair : temp) {
// Check if i, j, k
// and l are distinct
// or not
if (pair.index1 != i
&& pair.index1 != j
&& pair.index2 != i
&& pair.index2 != j) {
ArrayList<Integer> values
= new ArrayList<>();
values.add(
nums.get(pair.index1));
values.add(
nums.get(pair.index2));
values.add(nums.get(i));
values.add(nums.get(j));
// Sort the list to
// avoid duplicacy
Collections.sort(values);
// Update the hashset
ans.add(values);
}
}
}
}
}
// Print all the Quadruplets
for (ArrayList<Integer> arr : ans) {
System.out.println(arr);
}
}
// Driver Code
public static void main(String[] args)
{
ArrayList<Integer> arr = new ArrayList<>();
arr.add(1);
arr.add(0);
arr.add(-1);
arr.add(0);
arr.add(-2);
arr.add(2);
int K = 0;
GetQuadruplets(arr, K);
}
}
[-2, 0, 0, 2] [-1, 0, 0, 1] [-2, -1, 1, 2]
Complejidad de Tiempo: O(N 2 * log N)
Espacio Auxiliar: O(N 2 )