ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็มที่ไม่ซ้ำกันและผลรวม และเราต้องหาแฝดสามที่สามารถสร้างผลรวมได้
มาดูตัวอย่างในการแก้ปัญหากัน −
Input : array = {0 , 2 , -1 , 1, -2}
Sum = 1
Output : 1 2 -2
0 2 -1 เพื่อแก้ปัญหานี้ เราจะหาแฝดสามทั้งหมดที่ให้ผลรวม วิธีง่ายๆ ก็คือการใช้สามลูปและหาผลรวมขององค์ประกอบและคืนค่า triplet ที่เพียงพอ
ตัวอย่าง
#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
วิธีนี้สามารถทำให้มีประสิทธิภาพมากขึ้นโดยการจัดเรียงอาร์เรย์ซึ่งจะช่วยลดความซับซ้อนของพื้นที่ของโค้ด
