เราจะเห็นปัญหาหนึ่งที่น่าสนใจ เรามีอาร์เรย์ที่มีองค์ประกอบบางอย่าง มีค่าผลรวมหนึ่งค่า งานของเราคือค้นหาแฝดสามจากอาร์เรย์ และมีผลรวมเท่ากับผลรวมที่กำหนด สมมติว่าอาร์เรย์คือ {4, 8, 63, 21, 24, 3, 6, 1, 0} และค่าผลรวมคือ S =18 ดังนั้นแฝดสามจะเป็น {4, 6, 8} หากมีแฝดสามตัวมากกว่าหนึ่งตัว ก็จะแสดงทั้งหมด
อัลกอริทึม
getTriplets(arr, n, ผลรวม) −
Begin define one array to store triplets, say trip_arr define one set unique_trip to store unique triplets. No same triplets will be their. sort arr for i in range 0 to n-2, do j :- i + 1, and k := n – 1 while(j < k), do if arr[i] + arr[j] + arr[k] = sum, then temp := arr[i] : arr[j] : arr[k] if temp is not present into the unique_trip, then insert temp into unique_trip set create newTriplet using arr[i] arr[j] and arr[k] add newTriplet into trip_arr endif increase j, and decrease k else if arr[i] + arr[j] + arr[k] > sum decrease k else increase j end if done done display all triplets End
ตัวอย่าง
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
class triplet {
public:
int first, second, third;
void display() {
cout << "("<<first<<", "<<second<<", "<<third<<")" << endl;
}
};
int getTriplets(int arr[], int n, int sum) {
int i, j, k;
vector <triplet> triplets;
set <string> uniqTriplets; //use set to avoid duplicate triplets
string temp_triplet;
triplet newTriplet;
sort(arr, arr + n); //sort the array
for(i = 0; i < n - 2; i++) {
j = i + 1;
k = n - 1;
while(j < k) {
if(arr[i] + arr[j] + arr[k] == sum) {
temp_triplet = to_string(arr[i]) + " : " + to_string(arr[j]) + " : " + to_string(arr[k]);
if(uniqTriplets.find(temp_triplet) == uniqTriplets.end()) {
uniqTriplets.insert(temp_triplet);
newTriplet.first = arr[i];
newTriplet.second = arr[j];
newTriplet.third = arr[k];
triplets.push_back(newTriplet);
}
j++;
k--;
} else if(arr[i] + arr[j] + arr[k] > sum)
k--;
else
j++;
}
}
if(triplets.size() == 0)
return 0;
for(i = 0; i < triplets.size(); i++) {
triplets[i].display();
}
}
int main() {
int nums[] = {4, 8, 63, 21, 24, 3, 6, 1, 0, 5};
int n = sizeof(nums) / sizeof(nums[0]);
int sum = 27;
if(!getTriplets(nums, n, sum))
cout << "No triplets can be formed.";
} ผลลัพธ์
(0, 3, 24) (0, 6, 21) (1, 5, 21)
