【C++】ソート済み双方向連結リスト内で合計が指定値xと等しくなるトリプレットを数える方法

問題の概要

整数値を格納したソート済みの双方向連結リスト(doubly linked list)が与えられます。この問題の目的は、リストから3つのノードを選んだとき、そのデータ値の合計が指定された値 x と一致するようなトリプレット(3つ組)が何通り存在するかを数えることです。

たとえば、連結リストが 3 → 4 → 1 → 2 で x = 6 の場合、条件を満たすのは (3, 1, 2) だけなので、答えは 1 となります。

入力例 1

linked list: [ 3 − 4 − 13 − 5 − 10 − 10 − 0 ]  x = 20

出力

Count of triplets in a sorted doubly linked list whose sum is equal to a given value x are: 2

説明

条件を満たすトリプレットは次の2つです。
( 3, 4, 13 ) と ( 10, 10, 0 )

入力例 2

linked list: [ 4 − 3 − 1 − 5 − 2 − 4 − 2 ]  x = 8

出力

Count of triplets in a sorted doubly linked list whose sum is equal to a given value x are: 6

説明

条件を満たすトリプレットは次の6つです。
( 4, 3, 1 )、( 1, 5, 2 )、( 3, 1, 4 )、( 1, 5, 2 )、( 4, 2, 2 )、( 2, 4, 2 )

使用するアプローチ

本記事で紹介するプログラムでは、3重ループによる全探索(ブルートフォース)を用います。「ありうるすべての3ノードの組み合わせを調べ、合計が x になるものだけを数える」というシンプルな考え方です。具体的な手順は以下の通りです。

• int 型の data メンバと、自己参照的な next ポインタ・prev ポインタを持つ構造体として、連結リストのノードを定義します。
• 関数 insert_node(struct block** head, int data) は、指定されたデータを持つ新しいノードをリストの先頭に挿入します。
• 関数 sum_x(struct block* head, int x) は、双方向連結リストの先頭へのポインタと整数 x を引数に取り、データ部分の合計が x となるトリプレットの個数を返します。
• まずカウント用の変数 count を 0 で初期化します。
• struct block 型の3つのポインタ temp_1、temp_2、temp_3 を用意します。
• temp_1 をリストの先頭に、temp_2 をその次のノードに、temp_3 をさらにその次のノードに向け、先頭の3ノードを指す状態から処理を開始します。
• これら3つのポインタをネストしたループで末尾ノードに達するまで順に移動させながら走査します。
• 現在の3ノードのデータ部分の合計が x に等しい場合、すなわち (temp_1->data + temp_2->data + temp_3->data) == x が成り立つときに count を1増やします。
• ループが終了した時点で、条件を満たすトリプレットの総数が count に格納されています。
• 最後に count を結果として返します。

この手法の時間計算量は O(n³)(n はノード数)です。リストがソート済みであることを活かせば、二重ループと双方向ポインタを組み合わせた O(n²) の効率的な解法に改良できる点も覚えておくと良いでしょう。

C++での実装例

#include <iostream>
using namespace std;

struct block {
    int data;
    struct block *next, *prev;
};

void insert_node(struct block** head, int data){
    struct block* ptr = new block();
    ptr->data = data;
    ptr->next = NULL;
    ptr->prev = NULL;
    if ((*head) == NULL){
        (*head) = ptr;
    } else {
        ptr->next = *head;
        (*head)->prev = ptr;
        (*head) = ptr;
    }
}

int sum_x(struct block* head, int x){
    int count = 0;
    struct block *temp_1, *temp_2, *temp_3;
    for (temp_1 = head; temp_1 != NULL; temp_1 = temp_1->next){
        for (temp_2 = temp_1->next; temp_2 != NULL; temp_2 = temp_2->next){
            for (temp_3 = temp_2->next; temp_3 != NULL; temp_3 = temp_3->next){
                if ((temp_1->data + temp_2->data + temp_3->data) == x){
                    count++;
                }
            }
        }
    }
    return count;
}

int main(){
    struct block* head = NULL;
    insert_node(&head, 200);
    insert_node(&head, 100);
    insert_node(&head, 16);
    insert_node(&head, 14);
    insert_node(&head, 10);
    insert_node(&head, 10);
    insert_node(&head, 2);
    int x = 22;
    cout << "Count of triplets in a sorted doubly linked list whose sum is equal to a given value x are: " << sum_x(head, x);
    return 0;
}

出力

上記のコードをコンパイルして実行すると、次の出力が得られます。

Count of triplets in a sorted doubly linked list whose sum is equal to a given value x are: 1