C++で指定された合計ですべてのトリプレットを印刷します

この問題では、一意の整数の配列と合計が与えられます。そして、同じ合計を形成できるトリプレットを見つける必要があります。

問題を解決するために例を見てみましょう-

Input : array = {0 , 2 , -1 , 1, -2}
Sum = 1
Output : 1 2 -2
0 2 -1

この問題を解決するために、合計を提供するすべてのトリプレットを見つけます。簡単なアプローチは、3つのループを使用して要素の合計を見つけ、適切なトリプレットを返すことです。

例

#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（n ³ になるため、効率的ではありません。 ）3つのループを実行するため。そのため、他の手法を使用して、この問題を効果的に解決します。

1つの方法は、ハッシュを使用することです。この方法では、のすべての要素のペアを見つけて、それらが互いに補完し合うようにします。つまり、値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

この方法は、配列を並べ替えることでより効果的になり、コードのスペースの複雑さが軽減されます。