【C++】合計が指定した値に等しい2つの連結リストのペアを数える方法

2つの連結リストが与えられ、それぞれのリストに含まれる整数要素を組み合わせて、合計が指定した値(k)と等しくなるペアが何組作れるかを数えるのが本記事の課題です。連結リスト(linked list)とは、複数のデータ構造がリンク(ポインタ)で順々に接続されたデータ構造の列のことです。

入出力の確認

例1

vector<int> v_1 = {5, 7, 8, 10, 11};
vector<int> v_2 = {6, 4, 3, 2, 0};
int k = 11;

出力:

合計がkに等しいペアの個数: 4

解説: 2つのリストから作れる全25通りの組み合わせのうち、合計が11に一致するのは (5, 6)、(7, 4)、(8, 3)、(11, 0) の4組です。

例2

vector<int> v_1 = {2, 3, 5, 6};
vector<int> v_2 = {6, 4, 3};
int k = 6;

出力:

合計がkに等しいペアの個数: 2

解説: 全12通りの組み合わせのうち、合計が6に一致するのは (2, 4) と (3, 3) の2組です。

プログラムのアプローチ

• kの値と整数値を2つのvectorに入力し、それらをもとに連結リストを構築できるようにします。
• 引数として渡されたvectorから連結リストを作成する関数を作ります。
  • vectorのサイズ分だけループを回し、ListNodeクラスのポインタオブジェクトを作成します。
  • ptr->next がNULLでない間は ptr = ptr->next としてリスト末尾まで辿ります。
  • ptr->next に新しいノード(vector[i])を設定します。
  • 先頭ポインタstartを返します。
• 指定した合計に一致するペアの個数を返す関数を作ります。
  • カウント用の一時変数countを0で初期化します。
  • *first_list(1つ目のリスト用)と *second_list(2つ目のリスト用)という2つのポインタオブジェクトを用意します。
  • 外側のループで1つ目のリストを先頭から末尾まで走査します。
  • 内側のループで2つ目のリストを先頭から末尾まで走査します。
  • (first_list->data + second_list->data) == k が成立したらcountを1増やします。
  • 最後にcountを返します。
• 結果を出力します。

この手法はすべてのペアを総当たりで調べる方法で、時間計算量はO(n × m)(n, mは各リストの長さ)となります。

C++実装例

#include<bits/stdc++.h>
using namespace std;

class ListNode {
public:
    int data;
    ListNode *next;
    ListNode(int data) {
        this->data = data;
        next = NULL;
    }
};

// vectorから連結リストを作成する関数
ListNode *CreateList(vector<int> v) {
    ListNode *start = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ListNode *ptr = start;
        while (ptr->next != NULL) {
            ptr = ptr->next;
        }
        ptr->next = new ListNode(v[i]);
    }
    return start;
}

// 合計がkに等しいペアの個数を数える関数
int sum_pair(ListNode *start_1, ListNode *start_2, int k) {
    int count = 0;
    ListNode *first_list, *second_list;
    for (first_list = start_1; first_list != NULL; first_list = first_list->next) {
        for (second_list = start_2; second_list != NULL; second_list = second_list->next) {
            if ((first_list->data + second_list->data) == k) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    vector<int> v_1 = {5, 7, 8, 10, 11};
    ListNode* start_1 = CreateList(v_1);
    vector<int> v_2 = {6, 4, 3, 2, 0};
    ListNode* start_2 = CreateList(v_2);
    int k = 11;
    cout << "合計がkに等しいペアの個数: " << sum_pair(start_1, start_2, k);
}

実行結果

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

合計がkに等しいペアの個数: 4

まとめ

本記事では、2つの連結リストを二重ループで総当たり的に走査することで、合計が指定値kに等しいペアの個数を求める方法を解説しました。シンプルで理解しやすい手法ですが、リストが長くなると計算量が増大します。効率化したい場合は、片方のリストの要素をunordered_setに格納しておき、もう片方の各要素に対して「k − 要素」が存在するかをO(1)で判定する方法があり、この場合はO(n + m)まで計算量を抑えられます。