数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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 << "No triplets can be formed.";
}输出
(0, 3, 24) (0, 6, 21) (1, 5, 21)
更新于：20-8-2019
340 次浏览
广告