合計がC++の指定された値xに等しい2つのソートされた配列からペアをカウントします

正の数と値xを含む2つの配列が与えられます。目標は、タイプ（A、B）のペアがA + B =xであり、Aが最初の配列に属し、Bが2番目の配列に属するような配列の要素のペアを見つけることです。

例を挙げて理解しましょう

入力 − arr_1 [] ={1,2,5,3,4}; arr_2 [] ={7,0,1,3}; x =6

出力 −合計が指定された値xに等しい2つのソートされた配列からのペアの数は− 2

説明 −ペアは（5,1）-（arr_1 [2]、arr_2 [2]）と（3,3）-（arr_1 [3]、arr_2 [3]）

入力 − arr_1 [] ={1,1,1}; arr_2 [] ={2,2}; x =6

出力 −合計が指定された値xに等しい2つのソートされた配列からのペアの数は− 2

説明 −ペアは（1,2）-（arr_1 [0]、arr_2 [0]）と（1,2）-（arr_1 [1]、arr_2 [1]）

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

2つのアプローチを使用します。 forループを使用した最初の素朴なアプローチ。インデックスiがarr_1[]用で、インデックスjがarr_2 []用であるように、forループを使用して両方のトラバースを開始します。ペア（arr_1 [i] + arr_2 [j] ==x）の場合、カウントをインクリメントします。結果としてカウントを返します。

• size_arr_1およびsize_arr_2として正の要素と長さを持つ整数配列arr_1[]およびarr_2[]を取ります。

• 関数Pair_value_x（int arr_1 []、int arr_2 []、int size_arr_1、int size_arr_2、int x）は、配列とその長さの両方を取り、要素の合計がxになるようにペアを返します。

• countの初期値を0とします。

• arr_1[]をi=0からiにトラバースし始めます。

• arr_1 [i]、arr_2 [j]のペアごとに、合計がxであるかどうかを確認します。 trueの場合、カウントをインクリメントします。

• 結果としてカウントを返します。

効率的なアプローチ

このアプローチでは、arr_1の要素のunordered_setを作成します。次に、forループと各値arr_2 [i]を使用してarr_2をトラバースします。セット内で、x-arr_2 [i]が見つかった場合は、カウントをインクリメントします。最後にカウントを返します。

• 同じアレイとそのサイズを使用します。

• 関数Pair_value_x（int arr_1 []、int arr_2 []、int size_arr_1、int size_arr_2、int x）は、配列とその長さの両方を取り、要素の合計がxになるようにペアを返します。

• 初期カウントを0とします。

• arr_1の一意の要素を格納するためのunordered_sethash_mapを作成します。

• forループを使用してhash_mapにarr_1の要素を入力します。

• 次に、forループを使用してarr_2[]をトラバースします。

• arr-2 [j]ごとに、（hash_map.find（x --arr_2 [j]）！=hash_map.end（））を使用してhash_mapでx-arr_2 [j]が見つかった場合は、カウントをインクリメントします。

• 最後に、合計がxに等しいペアとしてカウントします。

• 結果としてカウントを返します。

例（素朴なアプローチ）

#include <bits/stdc++.h>
using namespace std;
int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x){
   int count = 0;
   for (int i = 0; i < size_arr_1; i++){
      for (int j = 0; j < size_arr_2; j++){
         if ((arr_1[i] + arr_2[j]) == x){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr_1[] = {1, 2, 3, 4};
   int arr_2[] = {2, 3, 4, 5};
   int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
   int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
   int x = 6;
   cout<<"Count of pairs from two sorted arrays whose sum is equal to a given value x are: "<<
Pair_value_x(arr_1, arr_2, size_arr_1 , size_arr_2, x);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of pairs from two sorted arrays whose sum is equal to a given value x are: 4

例（効率的なアプローチ）

#include <bits/stdc++.h>
using namespace std;
int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x){
   int count = 0;
   unordered_set<int> hash_map;
   for (int i = 0; i < size_arr_1; i++){
      hash_map.insert(arr_1[i]);
   }
   for (int j = 0; j < size_arr_2; j++){
      if (hash_map.find(x - arr_2[j]) != hash_map.end()){
         count++;
      }
   }
   return count;
}
int main(){
   int arr_1[] = {1, 2, 3, 4};
   int arr_2[] = {2, 3, 4, 5};
   int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
   int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
   int x = 6;
   cout<<"Count of pairs from two sorted arrays whose sum is equal to a given value x are: "<< Pair_value_x(arr_1, arr_2, size_arr_1 , size_arr_2, x);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of pairs from two sorted arrays whose sum is equal to a given value x are: 4