C++で最も多く出現する合計ペアをすべて出力する方法

問題の概要

この問題では、n個の一意な整数からなる配列が与えられます。その中から、配列内の2つの整数の和（ペアの合計値）を求め、その合計値が最大頻度で出現するものをすべて見つけて出力する必要があります。

この問題には複数の解が存在する場合があり、該当するすべての解を出力しなければなりません。

入力例と出力例

入力 : array = { 1, 12, 5, 7, 9, 11}
出力 : 16 12

説明： 合計16と12は、それぞれ2回出現しています。

5 + 11 = 16 ＆ 7 + 9 = 16
1 + 11 = 12 ＆ 5 + 7 = 12

解決のアプローチ

この問題を解くための基本的なアプローチは、すべてのペアの合計値の出現回数を調べ、その中で最も多く出現した合計値を持つペアを出力することです。

解決手順

ステップ1: すべてのペアを反復処理する。
ステップ2: ハッシュテーブルを使って各合計値の出現回数をカウントする。
ステップ3: 反復処理が完了したら、出現回数が最大の合計値を出力する。

ハッシュテーブル（unordered_map）を使用することで、各合計値の出現回数をO(1)の平均時間で記録・参照でき、効率的に集計できます。全体の計算量は二重ループによりO(n²)となります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
void sumPairs(int a[], int n){
   unordered_map<int, int> pairSum;
   for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
         pairSum[a[i] + a[j]]++;
      }
   }
   int occur = 0;
   for (auto it : pairSum) {
      if (it.second > occur) {
         occur = it.second;
      }
   }
   for (auto it : pairSum) {
      if (it.second == occur)
         cout << it.first <<"\t";
   }
}
int main(){
   int a[] = { 1, 12, 5, 7, 9, 11 };
   int n = sizeof(a) / sizeof(a[0]);
   cout<<"The sum pairs with max occurrence are : "<<endl;
   sumPairs(a, n);
   return 0;
}

実行結果

最大出現回数の合計ペアは以下の通りです。

16 12

コードの解説

このプログラムの動作を順に見ていきましょう。

1. ペアの合計値の集計： 関数sumPairs内で、入れ子になったループにより配列内のすべての要素ペア（i, j）を走査し、その和をキーとしてunordered_mapに出現回数を記録していきます。

2. 最大出現回数の特定： ハッシュテーブルを走査し、最も高い出現回数（occur）を求めます。

3. 結果の出力： 出現回数がoccurと一致するすべての合計値を出力します。これにより、最大頻度の合計値が複数存在する場合でも、すべてが出力されます。

まとめ

本記事では、C++を用いて配列内のペアの合計値の中から、最も頻繁に出現する合計値をすべて検出して出力する方法を紹介しました。ハッシュテーブルによる出現回数の管理は、この種の頻度集計問題において非常に有効な手法です。同様のアプローチは、「最頻出要素の検出」や「部分和のカウント」など、他の多くのアルゴリズム問題にも応用できます。