数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中打印具有给定和的三元组
在这个问题中，我们给定一个唯一整数数组和一个总和。我们需要找到可以构成相同总和的三元组。
让我们举个例子来解决这个问题：
Input : array = {0 , 2 , -1 , 1, -2}
Sum = 1
Output : 1 2 -2
0 2 -1为了解决这个问题，我们将找到所有能提供总和的三元组。一个简单的方法是使用三个循环，找到元素的和并返回合适的三元组。
示例
#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(n3)。因此，我们将使用其他技术以有效的方式解决此问题。
一种方法是使用哈希。在这种方法中，我们将找到每一对元素，使得它们互为补数，即对于值为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
通过对数组进行排序，可以使这种方法更有效，从而降低代码的空间复杂度。
更新于：2020年1月17日
213 次浏览
广告