在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)
热门推荐
10 新年门口花束祝福语简短
11 盘锦结婚祝福语大全简短
12 父母生日祝福语 简短独特
13 家庭恩爱祝福语简短英文
14 高考俄语祝福语大全简短
15 虎年祝福语 诗句唯美简短
16 生日婚礼祝福语简短精辟
17 虎年喝酒拜年祝福语简短
18 教师闺蜜祝福语简短