用C ++打印给定总和的所有三胞胎

• Z时代
• 2024-01-10
• 分类：综合

在这个问题中，我们得到了一个由唯一整数和和组成的数组。而且我们必须找到可以形成相同总和的三元组。

让我们以一个例子来解决这个问题-

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;
            }
         }
      }
   }
}
//驱动程式码
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 ³）。因此，我们将使用其他技术来有效解决此问题。

一种方法是使用哈希。在这种方法中，我们将找到的每个元素对，使它们彼此互补，即对于值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

通过对数组排序可以使此方法更有效，这将减少代码的空间复杂度。

以上是 用C ++打印给定总和的所有三胞胎 的全部内容， 来源链接： utcz.com/z/348970.html