C++で配列内から指定した合計値になるトリプレット（3つの要素）を見つける方法

このチュートリアルでは、配列の中から合計が指定された値と一致する3つの要素（トリプレット）を見つけるプログラムをC++で作成します。

解き方の手順

以下のステップで問題を解いていきます。

• テスト用のダミーデータを含む配列を作成します。

• 3つの要素を走査するため、三重のネストされたループを記述します。各ループは配列の末尾まで繰り返します。

  • 選んだ3つの要素を加算します。

  • その合計を指定された値と比較します。

  • 両者が一致した場合、該当する要素を出力してループを抜けます。

実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool findTriplet(int arr[], int arr_size, int sum) {
    for (int i = 0; i < arr_size - 2; i++) {
        for (int j = i + 1; j < arr_size - 1; j++) {
            for (int k = j + 1; k < arr_size; k++) {
                if (arr[i] + arr[j] + arr[k] == sum) {
                    cout << arr[i] << " " << arr[j] << " " << arr[k] << endl;
                    return true;
                }
            }
        }
    }
    return false;
}
int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
    findTriplet(arr, 7, 12);
    return 0;
}

出力

上記のプログラムを実行すると、次のような結果が得られます。

1 4 7

計算量に関する補足

このアプローチでは三重ループを使用しているため、時間計算量はO(n³)になります。配列サイズが大きくなると処理に時間がかかる点に注意してください。より効率的な解法としては、ソート後にツーポインタ法を組み合わせる、あるいはハッシュセットを活用する方法があり、これらにより計算量をO(n²)まで改善できます。

まとめ

この記事では、ブルートフォース（全探索）によるシンプルな実装で、配列内から合計が指定値と一致するトリプレットを見つける方法を学びました。本チュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。