C++で指定された合計値になるペアの数を数える方法

整数型の配列と目標となる合計値(sum)が与えられたとき、配列の要素から作れるすべてのペアのうち、2つの要素の和が指定された合計値と一致するペアが何組あるかを数えるのがこの課題です。

具体例

例1

入力: int arr[] = {2, 8, 1, 5, 11}、sum = 13

出力: 合計が13になるペアの数 ― 2

説明: 配列から作れる全ペアとその和は次の表の通りです。和が13になるのは (2, 11) と (8, 5) の2組であることがわかります。

例2(負の値を含む場合)

入力: int arr[] = {2, 8, 1, 5, -11}、sum = 6

出力: 合計が6になるペアの数 ― 1

説明: 配列に負の値が含まれていても考え方は同じです。全ペアの和を確認すると、和が6になるのは (1, 5) の1組だけです。

プログラムで使用するアプローチ

• ペアを作る対象となる整数要素の配列と、目標の合計値を入力として受け取ります。
• 配列のサイズを計算し、そのデータを処理用の関数に渡します。
• 指定された合計と一致するペアを数えるための一時変数 count を用意します。
• 外側の for ループを i = 0 から配列サイズ未満まで回します。
• 内側の for ループを j = i + 1 から配列サイズ未満まで回し、同じ組み合わせを重複して数えないようにします。
• ループ内で一時変数 total に arr[i] + arr[j] を代入します。
• total == sum であれば count を1増やします。
• ループが終わったら count を返します。
• main 関数で結果を出力します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
//指定された合計を持つペアを数える
int Pair_Sum(int arr[], int size, int sum){
    int count = 0;
    for (int i=0; i<size; i++){
        for (int j=i+1; j<size; j++){
            int total = arr[i] + arr[j];
            if (total == sum){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = {2, 6, 1, 7, 9, 8};
    int sum = 9;
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Count of pairs with given sum "<<sum<<" is: "<<Pair_Sum(arr, size, sum);
    return 0;
}

出力

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

Count of pairs with given sum 9 is: 2

計算量と補足

このアプローチでは、すべてのペアを総当たりで確認するため、時間計算量は O(n²)、追加のメモリ使用量は O(1) となります。配列のサイズが小さい場合は十分実用的ですが、要素数が多い場合には unordered_map や unordered_set を活用すると効果的です。「sum − 現在の要素」がすでに登場しているかを O(1) で判定できるため、全体の処理を O(n) まで高速化できます。