C++で2つの配列の共通要素の合計を求める方法

この問題では、すべての要素が互いに異なる（ユニークな値を持つ）2つの配列 arr1[] と arr2[] が与えられます。私たちのタスクは、2つの配列に共通して存在する要素の合計（オーバーラップサム）を求めることです。

問題の概要

両方の配列に出現する要素をすべて見つけ、その合計値を返します。共通要素は各配列に1つずつ存在するため、1つの共通要素につき値を2回加算することになります。

具体例で理解しよう

入力：

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

出力：

26

解説

両方の配列に存在する要素は「9」と「4」です。
合計は 9 + 9 + 4 + 4 = 26 となります。

解決アプローチ

方法1：全探索（ブルートフォース）

最もシンプルな方法は、片方の配列（例えば arr1[]）を走査し、各要素についてもう一方の配列内に一致する値が存在するかどうかを確認することです。一致する要素が見つかった場合は、その値を合計に2回加算します。

しかし、この方法ではループの入れ子構造が必要となるため、時間計算量は O(N²) となり、配列サイズが大きくなると非効率です。

方法2：ハッシュを活用した効率的な手法

より効率的な解決策としてハッシュテーブル（unordered_map）を使用する方法があります。手順は以下の通りです。

1. ハッシュテーブルを作成し、両方の配列の要素を格納しながら各要素の出現回数（頻度）を記録します。
2. 走査後、出現回数が2になっている要素（＝両方の配列に存在する要素）のみを取り出して合計します。
3. 合計値を2倍して返します。

このアプローチにより、時間計算量は O(N) まで削減できます。

実装例

以下は、上記のソリューションの動作を示すC++プログラムです。

#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

まとめ

2つの配列の共通要素の合計を求める問題は、ハッシュテーブルを活用することで O(N) の時間計算量で効率的に解くことができます。要素の頻度を記録し、出現回数が2の要素だけを集めて合計を2倍するというシンプルな発想がポイントです。