找到一个三元组，使得两个和等于C ++中的第三个元素

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

假设有一个n个数字的数组。我们必须找到三个数字，以使两个元素的总和与第三个元素相同。因此，如果数组类似于[5、32、1、7、10、50、19、21、2]，则输出将为21、2、19。如果未找到此类元素，则显示该消息。

为了解决这个问题，我们将遵循以下步骤-

  • 给定数组排序

  • 然后，从最后一个元素开始固定最大的元素，并遍历数组以找到其他两个数字，它们加起来等于第三个元素。

  • 取两个指针j和k，j从第一个开始，k从最后一个开始，从i-1中找到两个数字中的最小值，以找到其余两个数字中的最大值。

  • 如果两个数字的和仍小于Arr [i]，则我们必须增加两个数字之和的值，从而增加j指针，从而增加Arr [j] + Arr [ k]

  • 如果两个数字的总和大于Arr [i]，则我们需要减小两个数字之和的值，从而减小指针k，从而减小Arr [j] + Arr [k的总值]

示例

#include<iostream>
#include<algorithm>
#define N 5
using namespace std;
void getValueTriplet(int arr[], int n) {
   sort(arr, arr + n);
   for (int i = n - 1; i >= 0; i--) {
      int j = 0;
      int k = i - 1;
      while (j < k) {
         if (arr[i] == arr[j] + arr[k]) {
            cout << "The numbers are " << arr[i] << " " << arr[j] << " " << arr[k] << endl;
            return;
         }
         else if (arr[i] > arr[j] + arr[k])
         j += 1;
         else
         k -= 1;
      }
   }
   cout << "No such triplet exists";
}
int main() {
   int arr[] = { 5, 32, 1, 7, 10, 50, 19, 21, 2 };
   int n = sizeof(arr) / sizeof(arr[0]);
   getValueTriplet(arr, n);
}

输出结果

The numbers are 21 2 19

以上是 找到一个三元组，使得两个和等于C ++中的第三个元素 的全部内容， 来源链接： utcz.com/z/338240.html

回到顶部