C++を使用して2つの配列の重複する合計を見つけます

この問題では、一意の値で構成される2つの配列arr1[]とarr2[]が与えられます。私たちのタスクは、2つの配列の重複する合計を見つけることです。

配列のすべての要素は異なります。そして、両方の配列に共通する要素の合計を返す必要があります

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

入力

arr1[] = {5, 4, 9, 2}, arr2[] = {6, 3, 9, 4}

出力

2

説明

The elements that are present in both arrays are 9 and 4.
The sum is 9 + 9 + 4 + 4 = 26

ソリューションアプローチ

この問題の簡単な解決策は、arr1 []などの1つの配列をトラバースし、各要素について、別の配列に一致する値があるかどうかを確認することです。現在の値に一致する要素が見つかった場合は、両方を合計値に追加します。

このアプローチでは、ループのネストが必要であり、O（N ² の次数の時間計算量につながります。 。

この問題を解決する別のアプローチは、ハッシュを使用することです。ハッシュテーブルを作成し、両方の配列の値をテーブルに格納し、要素の頻度のカウントを保持します。次に、発生頻度が2の値を追加します。合計値の2倍を返します。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
int findCommonValSum(int A[], int B[], int n){
   unordered_map<int,int> hashTable;
   for(int i=0;i<n;i++){
      if(hashTable.find(A[i])==hashTable.end())
      hashTable.insert(make_pair(A[i],1));
      else
         hashTable[A[i]]++;

      if(hashTable.find(B[i])==hashTable.end())
         hashTable.insert(make_pair(B[i],1));
      else
      hashTable[B[i]]++;
   }
   int commSum = 0;
   for(auto itr = hashTable.begin(); itr!=hashTable.end(); itr++){
      if((itr->second)==2){
         commSum += (itr->first);
      }
   }
   return (commSum*2);
}
int main(){
   int A[] = { 5, 4, 9, 2 };
   int B[] = { 6, 3, 9, 4 };
   int n = sizeof(A) / sizeof(A[0]);
   cout<<"The sum of common values in the array are "<<findCommonValSum(A, B, n);
   return 0;
}

出力

The sum of common values in the array are 26