C++で2つの要素の和が3番目の要素と等しくなるトリプレットを見つける方法

n個の数値からなる配列があるとします。この中から「2つの要素の和が、もう1つの要素と等しくなる」ような3つの数値(トリプレット)を見つける必要があります。

例えば、配列が [5, 32, 1, 7, 10, 50, 19, 21, 2] の場合、出力は 21, 2, 19 となります(2 + 19 = 21)。該当する組み合わせが存在しない場合は、その旨のメッセージを表示します。

アルゴリズムの考え方

この問題を解決するには、以下の手順に従います。

• まず、与えられた配列を昇順にソートします。
• 次に、配列の末尾(最大の要素)から順に要素を固定し、その要素と等しくなるような和を持つ2つの数値を探索します。
• 2つのポインタ j(先頭から)と k(i - 1 の位置から)を用意し、範囲内の最小値と最大値を効率よく探します。
• 2つの数値の和が Arr[i] より小さい場合は、和を増やす必要があるため、ポインタ j を1つ進めます(これにより Arr[j] + Arr[k] の値が大きくなります)。
• 2つの数値の和が Arr[i] より大きい場合は、和を減らす必要があるため、ポインタ k を1つ戻します(これにより Arr[j] + Arr[k] の値が小さくなります)。

この手法により、ソート後の配列に対して各要素を固定しながら2ポインタ法を適用することで、効率的にトリプレットを発見できます。

サンプルコード

#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

計算量について

このアルゴリズムの時間計算量は、ソートに O(n log n)、その後の探索に O(n²) かかるため、全体として O(n²) となります。素朴な全組み合わせを試す方法(O(n³))と比較して、大幅に効率化されている点がポイントです。