C++で指定された配列に合計が存在する個別のペアの数をカウントします

たとえば、任意のサイズの整数値のarr []の配列が与えられます。タスクは、同じ配列にも合計が存在する、特定の配列で使用可能な個別のペアの数のカウントを計算することです。

配列は、同じタイプの要素の固定サイズの順次コレクションを格納できる一種のデータ構造です。配列はデータのコレクションを格納するために使用されますが、配列を同じタイプの変数のコレクションと考える方が便利な場合がよくあります。

覚えておくべきポイント

• ペアは、順序に関係なく、同じ要素で1回カウントされます。たとえば、（3,2）と（2,3）は1としてカウントされます。

• 配列内に複数回出現する数がある場合、それは1つのペアを形成するために正確に2回と見なされます。たとえば、配列に{2、2、2、2}の要素がある場合、ペアは（2,2）になり、1としてカウントされます。

例

Input − int arr = {6, 4, 10, 14}
Output − count is 2

説明 −配列内の合計とのペアは（6,4）と（10,4）であるため、カウントは2です

Input − int arr = {6, 6, 6 ,6, 6, 13}
Output − count is 0

説明 −同じ配列の合計とのペアは配列にありません。したがって、カウントは0です。

以下のプログラムで使用されているアプローチは次のとおりです

• 配列を作成します。たとえば、arr []

• 配列内の要素ごとに整数値を返すlength（）関数を使用して、配列の長さを計算します。

• 要素の数を格納する一時変数を取ります。

• マップタイプ変数を作成します。たとえば、mp

• iを0に設定し、iが配列のサイズよりも小さい場合にループを開始します

• ペア型変数の別のマップを作成します。たとえば、par

• iを0に設定し、iが配列のサイズよりも小さい場合にループを開始します

• ループ内で、jからi + 1で、jが配列のサイズよりも小さい別のループを開始します

• ループ内で、mp [arr [i] + arr [j]]> 0 AND pr [{arr [i]、arr [j]}] =0かどうかを確認してから、カウントを1増やします

• par [{arr [i]、arr[j]}]を1ずつ増やします

• par [{arr [j]、arr[i]}]を1ずつ増やします

• カウントを返す

• 結果を印刷します。

例

#include <iostream>
#include <map>
using namespace std;
// Returns number of pairs in ar[0..n-1] with
// sum equal to 'sum'
int countpairs(int ar[], int n){
   // Store counts of all elements in map m
   // to find pair (ar[i], sum-ar[i])
   // because (ar[i]) + (sum - ar[i]) = sum
   map<int, int> mymap;
   for (int i = 0; i < n; i++){
      mymap[ar[i]]++;
   }
   // To remove duplicate items we use result map
   map<pair<int, int>, int> p;
   int result = 0;
   // Considering all pairs
   for (int i = 0; i < n; i++){
      for (int j = i + 1; j < n; j++){
         // If sum of current pair exists
         if (mymap[ar[i] + ar[j]] > 0 && p[{ ar[i], ar[j] }] ==0){
            result++;
         }
         // Inserting the current pair both ways to avoid
         // duplicates.
         p[{ ar[i], ar[j] }]++;
         p[{ ar[j], ar[i] }]++;
      }
   }
   return result;
}
// main function
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