이 문제에서는 고유한 정수 배열과 합계가 제공됩니다. 그리고 우리는 같은 합을 형성할 수 있는 삼중항을 찾아야 합니다.
문제를 해결하기 위해 예를 들어 보겠습니다 -
Input : array = {0 , 2 , -1 , 1, -2}
Sum = 1
Output : 1 2 -2
0 2 -1 이 문제를 해결하기 위해 우리는 합을 제공하는 모든 삼중항을 찾을 것입니다. 간단한 접근 방식은 3개의 루프를 사용하고 요소의 합을 찾고 적절한 삼중항을 반환하는 것입니다.
예시
#include <iostream>
using namespace std;
void Triplets(int arr[], int n, int sum){
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == sum) {
cout<<arr[i]<<"\t"<<arr[j]<<"\t"<<arr[k]<<endl;
}
}
}
}
}
// Driver code
int main(){
int arr[] = { 0 , 2 , -1 , 1, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The Triplets are : \n";
Triplets(arr, n, 1);
return 0;
} 출력
세쌍둥이는 -
0 2 -1 2 1 -2
그러나 이 접근 방식은 o(n 3 의 시간 복잡도를 갖기 때문에 효율적이지 않습니다. ) 세 개의 루프를 실행합니다. 따라서 우리는 이 문제를 효과적인 방법으로 해결하기 위해 다른 기술을 사용할 것입니다.
한 가지 방법은 해싱을 사용하는 것입니다. 이 방법에서 우리는 서로 보완이 되도록 의 모든 요소의 쌍을 찾을 것입니다. 즉, 값이 x인 요소의 경우 요소 -x가 필요합니다.
이렇게 하면 코드의 시간 복잡성이 줄어듭니다.
예시
#include <bits/stdc++.h>
using namespace std;
void Triplets(int arr[], int n, int sum{
for (int i = 0; i < n - 1; i++) {
unordered_set<int> triplet;
for (int j = i + 1; j < n; j++) {
int third = sum - (arr[i] + arr[j]);
if (triplet.find(third) != triplet.end())
cout<<third<<"\t"<<arr[i]<<"\t"<<arr[j]<<endl;
else
triplet.insert(arr[j]);
}
}
}
int main(){
int arr[] = { 0 , 2 , -1 , 1, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The Triplets are : \n";
Triplets(arr, n, 1);
return 0;
} 출력
세쌍둥이는 -
0 2 -1 2 1 -2
이 방법은 코드의 공간 복잡성을 줄이는 배열을 정렬하여 더 효과적으로 만들 수 있습니다.