在C ++中所有总计给定值的唯一三元组
在这里，我们将看到一个有趣的问题。我们有一个包含一些元素的数组。给出一个总和值。我们的任务是从数组中查找三元组，其总数与给定的总数相同。假设数组为{4，8，63，21，24，3，6，1，0}，总和为S=18。所以三元组将为{4，6，8}。如果存在多个三元组，它将显示所有这些三元组。
算法
getTriplets(arr,n,sum)-
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 << "无法形成三胞胎。";
}输出结果
(0, 3, 24) (0, 6, 21) (1, 5, 21)