C++で3つの連結リストから合計が指定値と一致するトリプレットを見つける方法

このチュートリアルでは、C++を使って、3つの連結リスト（リンクリスト）から、それぞれ1要素ずつ選んだ3つの値の合計が指定された数と一致する組み合わせ（トリプレット）を見つけるプログラムを作成します。

解決のアプローチ

最もシンプルな方法は、ブルートフォース（総当たり）です。各リストの全要素を順番に組み合わせて、合計が目標値と一致するかどうかを確認します。手順は以下の通りです。

• 連結リスト用のノード構造体（struct）を定義します。

• ダミーデータを使って3つの連結リストを作成します。

• 3重のネストしたループを書き、各リストの先頭から末尾まで要素を走査します。

  • 現在走査中の3つの要素の合計を計算します。

  • 合計が指定された数と一致するか比較します。

  • 一致していれば、その3つの要素を出力し、すべてのループを抜けます。

このアルゴリズムの計算量は O(n³) です。リストのサイズが小さい場合は十分実用的ですが、大きなデータセットにはハッシュやソート＋ポインタを活用した最適化手法があります。

サンプルコード

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

#include <bits/stdc++.h>
using namespace std;
class Node {
    public:
    int data;
    Node* next;
};
void insertNewNode(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    *head_ref = new_node;
}
void findTriplet(Node *head_one, Node *head_two, Node *head_three, int givenNumber) {
    bool is_triplet_found = false;
    Node *a = head_one;
    while (a != NULL) {
        Node *b = head_two;
        while (b != NULL) {
            Node *c = head_three;
            while (c != NULL) {
                int sum = a->data + b->data + c->data;
                if (sum == givenNumber) {
                    cout << a->data << " " << b->data << " " << c->data << endl;
                    is_triplet_found = true;
                    break;
                }
                c = c->next;
            }
            if (is_triplet_found) {
                break;
            }
            b = b->next;
        }
        if (is_triplet_found) {
            break;
        }
        a = a->next;
    }
    if (!is_triplet_found) {
        cout << "No triplet found" << endl;
    }
}
int main() {
    Node* head_one = NULL;
    Node* head_two = NULL;
    Node* head_three = NULL;
    insertNewNode (&head_one, 4);
    insertNewNode (&head_one, 3);
    insertNewNode (&head_one, 2);
    insertNewNode (&head_one, 1);
    insertNewNode (&head_two, 4);
    insertNewNode (&head_two, 3);
    insertNewNode (&head_two, 2);
    insertNewNode (&head_two, 1);
    insertNewNode (&head_three, 1);
    insertNewNode (&head_three, 2);
    insertNewNode (&head_three, 3);
    insertNewNode (&head_three, 4);
    findTriplet(head_one, head_two, head_three, 9);
    findTriplet(head_one, head_two, head_three, 100);
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

1 4 4
No triplet found

最初の呼び出しでは、合計が9になる組み合わせ「1 + 4 + 4」が見つかりました。一方、2回目の呼び出しでは合計が100になる組み合わせが存在しないため、「No triplet found」と表示されます。

まとめ

このチュートリアルでは、3つの連結リストから合計が指定値と一致するトリプレットを検索する基本的な方法を学びました。まずはシンプルな三重ループによる実装を理解し、その後パフォーマンスが必要になった段階でハッシュマップなどを利用した高速化に挑戦してみてください。チュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。