Dada una array arr de enteros de tamaño N y un número objetivo , la tarea es encontrar todos los cuatrillizos únicos en él, cuya suma sea igual al número objetivo.
Ejemplos:
Entrada: arr[] = {4, 1, 2, -1, 1, -3], objetivo = 1
Salida: [[-3, -1, 1, 4], [-3, 1, 1, 2] ]
Explicación:
la suma de ambos cuatrillizos es igual al objetivo.Entrada: arr[] = {2, 0, -1, 1, -2, 2}, objetivo = 2
Salida: [[-2, 0, 2, 2], [-1, 0, 1, 2]]
Enfoque de dos punteros:
este problema sigue el patrón de dos punteros y comparte similitudes con Triplet Sum to Zero .
Podemos seguir un enfoque similar para iterar a través de la array, tomando un número a la vez. En cada paso durante la iteración, buscaremos los cuatrillizos similares a Triplet Sum to Zero cuya suma sea igual al objetivo dado.
C++
// C++ program to find four
// elements that sum to a given value
#include <bits/stdc++.h>
using namespace std;
class QuadrupleSumToTarget {
public:
// Function to find quadruplets
static vector<vector<int> >
searchQuadruplets(
vector<int>& arr,
int target)
{
sort(arr.begin(), arr.end());
vector<vector<int> > quadruplets;
for (int i = 0; i < arr.size() - 3; i++) {
if (i > 0 && arr[i] == arr[i - 1]) {
// Skip same element
// to avoid duplicate
continue;
}
for (int j = i + 1; j < arr.size() - 2; j++) {
if (j > i + 1 && arr[j] == arr[j - 1]) {
// Skip same element
// to avoid duplicate quad
continue;
}
searchPairs(
arr, target,
i, j, quadruplets);
}
}
return quadruplets;
}
private:
// Function to search Quadruplets
static void
searchPairs(
const vector<int>& arr,
int targetSum, int first,
int second,
vector<vector<int> >& quadruplets)
{
int left = second + 1;
int right = arr.size() - 1;
while (left < right) {
int sum
= arr[first]
+ arr[second]
+ arr[left]
+ arr[right];
if (sum == targetSum) {
// Found the quadruplet
quadruplets
.push_back(
{ arr[first], arr[second],
arr[left],
arr[right] });
left++;
right--;
// Skip same element to avoid
// duplicate quadruplets
while (left < right
&& arr[left]
== arr[left - 1]) {
left++;
}
// Skip same element to avoid
// duplicate quadruplets
while (left < right
&& arr[right]
== arr[right + 1]) {
right--;
}
}
// We need a pair
// with a bigger sum
else if (sum < targetSum) {
left++;
}
// We need a pair
// with a smaller sum
else {
right--;
}
}
}
};
void printQuad(
vector<int>& vec, int target)
{
// Function call
auto result
= QuadrupleSumToTarget::
searchQuadruplets(
vec, target);
// Print Quadruples
for (int j = 0; j < result.size(); j++) {
vector<int> vec = result[j];
if (j == 0)
cout << "[";
for (int i = 0; i < vec.size(); i++) {
if (i == 0)
cout << "[";
cout << vec[i];
if (i != vec.size() - 1)
cout << ", ";
else
cout << "]";
}
if (j != result.size() - 1)
cout << ", ";
else
cout << "]";
}
}
// Driver code
int main(int argc, char* argv[])
{
vector<int> vec
= { 4, 1, 2,
-1, 1, -3 };
int target = 1;
printQuad(vec, target);
return 0;
}
[[-3, -1, 1, 4], [-3, 1, 1, 2]]
Complejidad del tiempo: Ordenar la array tomará O(N*logN) . En general , searchQuadruplets() tomará O(N * logN + N^3) , que es asintóticamente equivalente a O(N^3) .
Complejidad del espacio auxiliar : la complejidad del espacio auxiliar del algoritmo anterior será O (N) , que se requiere para la clasificación.
Artículos similares: