C ++で合計が等しい、ソートされていない配列のすべてのペアを出力します

この問題では、並べ替えられていない配列があり、この配列内で合計が等しいすべてのペアを出力する必要があります。

問題を理解するために例を見てみましょう-

Input: array = [12, 13, 20, 5]
Output: [12, 13] and [20, 5] have sum 25.

この問題を解決するには、同じ合計のペアを見つける必要があります。このために、同じ合計のペアをチェックします。また、ペアの重複を避けるために、マップを使用します。

このために、2つのマップが必要になります。1つはすべての合計ペアとその合計を格納し、もう1つはすべての合計とそれに対応するペアを格納します。

したがって、Map1→key=ペア;値→合計

Map2→key=整数の合計;値→ペアのベクトル

ここで、合計値が同じであるすべての値を出力します。

例

上記の論理を説明するプログラム-

#include <bits/stdc++.h>
using namespace std;
void findEqualSumPairs(int A[], int n){
   map<int, vector<pair<int, int> > >map1;
   for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
         pair<int, int> p = make_pair(A[i], A[j]);
         map1[A[i] + A[j]].push_back(p);
      }
   }
   for (auto value = map1.begin(); value != map1.end(); value++) {
      if (value->second.size() > 1) {
         for (int i = 0; i < value->second.size(); i++) {
            cout<<"[ "<<value->second[i].first<<", "<<value->second[i].second<<"] ";
         }
         cout<<"have sum : "<<value->first<<endl;
      }
   }
}
int main() {
   int A[] = { 6, 4, 12, 10, 22,11, 8, 2 };
   int n = sizeof(A) / sizeof(A[0]);
   cout<<"Pairs with same sum are : \n";
   findEqualSumPairs(A, n);
   return 0;
}

出力

同じ合計のペアは-

[ 6, 4] [ 8, 2] have sum : 10
[ 4, 8] [ 10, 2] have sum : 12
[ 6, 8] [ 4, 10] [ 12, 2] have sum : 14
[ 6, 10] [ 4, 12] have sum : 16
[ 6, 12] [ 10, 8] have sum : 18