C++で指定された合計値となるすべての一意なトリプレットを見つける方法

今回は、配列の中から3つの要素を選び、その合計が指定された値と一致する「トリプレット(三つ組)」をすべて見つけるという、興味深い問題を解説します。

問題の概要

いくつかの要素を含む配列と、目標となる合計値が与えられます。この中から合計が指定値と等しくなる3つの要素の組み合わせをすべて抽出するのがタスクです。

例えば、配列が {4, 8, 63, 21, 24, 3, 6, 1, 0} で、合計値 S = 27 が与えられた場合、条件を満たすトリプレットは {0, 3, 24}、{0, 6, 21}、{1, 5, 21} となります。条件を満たす組み合わせが複数存在する場合は、それらをすべて出力します。また、同じ組み合わせが重複して表示されないよう、「一意な」トリプレットのみを扱う点がポイントです。

アルゴリズム

この問題は、配列をソートした後に二ポインタ法(two-pointer technique)を使うことで効率的に解けます。大まかな流れは以下の通りです。

Begin
    トリプレットを格納する配列 trip_arr を定義する
    一意なトリプレットを格納する集合 unique_trip を定義する(重複排除用)
    配列 arr をソートする
    i を 0 から n-2 まで繰り返す:
        j := i + 1、k := n - 1 とする
        j < k の間、以下を繰り返す:
            もし arr[i] + arr[j] + arr[k] = sum ならば
                temp := arr[i] : arr[j] : arr[k]
                temp が unique_trip に存在しなければ
                    temp を unique_trip に挿入する
                    arr[i]、arr[j]、arr[k] から新しいトリプレットを作成し
                    trip_arr に追加する
                終了条件
                j を増やし、k を減らす
            そうでなく、arr[i] + arr[j] + arr[k] > sum ならば
                k を減らす
            そうでなければ
                j を増やす
            終了条件
        繰り返し終了
    繰り返し終了
    すべてのトリプレットを表示する
End

C++での実装例

以下は、上記のアルゴリズムをC++で実装したサンプルコードです。重複チェックには set<string> を使用しています。

#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; // setを使用して重複するトリプレットを回避
    string temp_triplet;
    triplet newTriplet;
    sort(arr, arr + n); // 配列をソート
    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 << "No triplets can be formed.";
}

実行結果

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

計算量について

このアプローチの計算量は O(n²) です。外側のループで各要素を固定し、内側では二ポインタ法により残りの範囲を線形時間で探索するため、全要素の組み合わせを総当たりする O(n³) の素朴な手法よりも大幅に高速です。ソートにかかる計算量 O(n log n) も含めると、全体として非常に効率的な解法と言えます。