資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告