C++で配列内の重複しない（一意な）要素の合計を求める方法

問題の概要

いくつかの要素を含む配列 A があるとします。この配列から、すべての一意な（重複しない）要素の合計を求める必要があります。

例えば、配列が A = [5, 12, 63, 5, 33, 47, 12, 63] の場合を考えてみましょう。このとき、一意な要素は「5, 12, 63, 33, 47」であり、その合計は 160 になります。重複している要素は、一度合計に加算された後は単純に無視されます。

解決のアプローチ

この問題は、C++の unordered_set（ハッシュセット）を使うことで効率的に解決できます。基本的な考え方は以下のとおりです。

• forループを1回だけ実行して配列を走査する
• 初めて現れた値であれば、合計変数に加算する
• 同時にハッシュテーブル（unordered_set）にその値を記録する
• 2回目以降に同じ値が現れた場合は、すでにセットに存在するため無視する

ハッシュセットによる検索・挿入は平均 O(1) で行えるため、全体の計算量は O(n) となり、非常に高速に処理できます。

コード例

#include<iostream>
#include<unordered_set>
using namespace std;

int getNonRepeatSum(int arr[], int n) {
    int sum = 0;
    unordered_set<int> u_set;
    for (int i = 0; i < n; i++) {
        // まだセットに存在しない値なら加算して登録
        if (u_set.find(arr[i]) == u_set.end()) {
            sum += arr[i];
            u_set.insert(arr[i]);
        }
    }
    return sum;
}

int main() {
    int arr[] = {5, 12, 63, 5, 33, 47, 12, 63};
    int n = sizeof(arr) / sizeof(int);
    cout << "Sum is: " << getNonRepeatSum(arr, n);
}

実行結果

Sum is: 160

コードのポイント

• u_set.find(arr[i]) == u_set.end() によって、その値がまだセットに存在しないこと（＝初登場であること）を判定しています。
• 初登場の値のみ sum に加算し、insert() でセットに登録することで、以降の重複を自動的に排除できます。
• ソート不要・二重ループ不要のため、要素数が多い配列でも高いパフォーマンスを発揮します。