在C ++中所有总计给定值的唯一三元组

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

在这里，我们将看到一个有趣的问题。我们有一个包含一些元素的数组。给出一个总和值。我们的任务是从数组中查找三元组，其总数与给定的总数相同。假设数组为{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 << "无法形成三胞胎。";
}

输出结果

(0, 3, 24)
(0, 6, 21)
(1, 5, 21)

以上是 在C ++中所有总计给定值的唯一三元组 的全部内容， 来源链接： utcz.com/z/343322.html