C++で指定された合計値となるすべてのトリプレットを出力する方法

この問題では、重複のない整数の配列と合計値が与えられ、その合計値と等しくなる3つの要素の組み合わせ（トリプレット）をすべて見つける必要があります。

まず、具体例を使って問題を確認してみましょう。

入力 : array = {0 , 2 , -1 , 1, -2}
Sum = 1
出力 : 1 2 -2
0 2 -1

この問題を解くには、合計値に一致するすべてのトリプレットを見つけます。最もシンプルなアプローチは、3重ループを使ってすべての要素の組み合わせの合計を計算し、条件に合致するトリプレットを出力する方法です。

方法1：3重ループによる全探索

#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;
}

出力

The Triplets are :
0 2 -1
2 1 -2

しかし、このアプローチでは3重ループを実行するため、時間計算量がO(n³)となり、大規模な配列に対しては非効率です。そこで、より効果的な手法を用いてこの問題を解決します。

その一つがハッシュ（unordered_set）を活用する方法です。この方法では、各要素について、残りの2つの要素の合計が補完関係になるペアを探します。具体的には、値xを持つ要素に対して、sum − x に相当する要素がすでに存在するかをハッシュセットで高速に判定します。

これにより、コードの時間計算量をO(n²)まで削減できます。

方法2：ハッシュを使用した効率的な解法

#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;
}

出力

The Triplets are :
0 2 -1
2 1 -2

さらに、配列を事前にソートすることで、この方法の空間計算量を削減し、より効率的にすることができます。ソート後は two-pointer（双方向ポインタ）テクニックを組み合わせることで、追加のメモリを使用せずに解くことも可能です。