C++で配列内に合計値が存在する個別のペアの数をカウントする方法

整数値からなる任意のサイズの配列 arr[] が与えられたとき、「その和も同じ配列内に存在する」個別のペアの数を計算するのが本記事のテーマです。

配列とは、同じ型の要素を固定サイズで連続的に格納できるデータ構造の一種です。データの集合を保持するために使われますが、実用上は「同じ型の変数の集まり」として捉えると理解しやすいことが多いでしょう。

押さえておくべきポイント

• ペアは要素の並び順にかかわらず、同じ組み合わせであれば1回のみカウントします。たとえば (3,2) と (2,3) は同一のペアとして1件と数えます。
• 配列内に複数回現れる値は、ペアを構成するうえでちょうど2つぶんまでしか考慮されません。たとえば配列の要素が {2, 2, 2, 2} の場合、成立するペアは (2,2) のみで、カウントは1となります。

具体例

入力 − int arr = {6, 4, 10, 14}
出力 − count is 2

解説 − 和が配列内に存在するペアは (6,4) と (10,4) の2つなので、カウントは2になります。

入力 − int arr = {6, 6, 6, 6, 6, 13}
出力 − count is 0

解説 − 和が同じ配列内に存在するペアがひとつもないため、カウントは0になります。

プログラムで採用しているアプローチ

• まず配列 arr[] を作成します。
• sizeof(ar) / sizeof(ar[0]) を使い、配列の長さ（要素数 n）を求めます。
• 各要素の出現回数を記録するためのマップ mymap を用意します。(ar[i]) + (sum − ar[i]) = sum の関係を利用することで、ペア候補を効率的に判定できます。
• i を 0 から配列サイズ未満の範囲でループさせます。
• 重複ペアの除外用に、pair 型をキーにもつもうひとつのマップ p を作成します。
• 外側のループ内で、j を i+1 から配列サイズ未満の範囲でループさせます。
• ループ内では、mymap[ar[i] + ar[j]] > 0 かつ p[{ar[i], ar[j]}] == 0 を満たす場合に限り、result を 1 増やします。
• p[{ar[i], ar[j]}] と p[{ar[j], ar[i]}] をそれぞれインクリメントし、順序が逆になるだけの重複登録を防ぎます。
• 最後に result を返却し、main 関数で結果を出力します。

サンプルコード

#include <iostream>
#include <map>
using namespace std;

// ar[0..n-1] の中から、和が配列内に存在する
// ペアの総数を返す関数
int countpairs(int ar[], int n){
    // すべての要素の出現回数をマップ mymap に記録。
    // (ar[i]) + (sum - ar[i]) = sum の関係から
    // ペア (ar[i], sum-ar[i]) を見つけやすくする。
    map<int, int> mymap;
    for (int i = 0; i < n; i++){
        mymap[ar[i]]++;
    }
    // 重複項目を除外するために結果用マップを使用
    map<pair<int, int>, int> p;
    int result = 0;
    // すべてのペアを走査
    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++){
            // 現在のペアの和が配列内に存在する場合
            if (mymap[ar[i] + ar[j]] > 0 && p[{ ar[i], ar[j] }] == 0){
                result++;
            }
            // 重複を避けるため、現在のペアを両方向で登録
            p[{ ar[i], ar[j] }]++;
            p[{ ar[j], ar[i] }]++;
        }
    }
    return result;
}

// main関数
int main(){
    int ar[] = { 6, 4, 10, 14 };
    int n = sizeof(ar) / sizeof(ar[0]);
    cout << "count is " << countpairs(ar, n);
    return 0;
}

出力結果

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

count is 2