C++で配列内の絶対値が同じ正負のペアを検索する方法

この記事では、重複のない要素を含む配列から、絶対値が同じである正の値と負の値のペアを見つけ、ソートされた順序で出力する方法を解説します。

入力 : arr[] = { 1, -1, 11, 12, 56, 77, -56, -12, -88}
出力 : -1 1 -12 12 -56 56

入力 : arr[] = {30, 40, 50, 77, -51, -50, -40}
出力 : -40 40 -50 50

解決アプローチの概要

まず思い浮かぶのが総当たり（ブルートフォース）法ですが、これに加えて、計算量を大幅に削減できる効率的な手法（ハッシュマップを利用した方法）もあります。ここでは両方のアプローチを詳しく見ていきましょう。

総当たり（ブルートフォース）法

この方法では、配列を走査しながら各要素について、絶対値は同じだが符号が異なる別の要素を探します。ペアが見つかった時点で内側のループを抜けることで、無駄な処理を減らしています。

サンプルコード

#include<bits/stdc++.h>
using namespace std;

int main() {
    int arr[] = { 1, -1, 11, 12, 56, 77, -56, -12, -88 };
    int n = sizeof(arr)/sizeof(int); // 配列のサイズ
    vector<int> nums; // 見つかったペアの絶対値を格納

    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            if(abs(arr[j]) == abs(arr[i])) { // ペアを検索
                nums.push_back(abs(arr[i]));
                break;
                // 配列の要素は重複がないため、
                // ペアが見つかり次第ループを抜けて問題ない
            }
        }
    }
    sort(nums.begin(), nums.end());
    for(auto x : nums) // ペアを出力
        cout << -x << " " << x << " ";
}

出力結果

-1 1 -12 12 -56 56

このアプローチでは、二重ループで配列を走査してペアとなる要素を探します。要素が見つかれば内側のループを抜けることで多少高速化できますが、全体の時間計算量は O(N²) となります。N は配列のサイズです。制約が小さい場合は問題ありませんが、大きなデータには不向きです。そこで次に紹介するのが、より効率的な方法です。

効率的な手法（ハッシュマップを使用）

このアプローチではハッシュマップ（連想配列）を活用することで、時間計算量を大幅に削減します。各要素の絶対値の出現回数を記録し、出現回数が2回（つまり正と負の両方が存在する）の値だけを取り出す仕組みです。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
int main() {
    int arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 };
    int n = sizeof(arr)/sizeof(int); // 配列のサイズ
    map<int, int> found; // 各数値の出現回数を記録
    vector<int> nums; // 見つかったペアの絶対値を格納

    for(int i = 0; i < n; i++)
        found[abs(arr[i])]++; // 絶対値の出現頻度をカウント

    for(auto x : found) { // マップを走査
        if(x.second == 2) // 出現回数が2ならペアが存在
            nums.push_back(x.first);
    }
    for(auto x : nums) // ペアを出力
        cout << -x << " " << x << " ";
}

出力結果

-1 1 -4 4 -8 8 -9 9

コードの解説

このアプローチでは、ハッシュマップを使って数値の出現頻度を管理します。配列を走査しながら、現在の要素の絶対値の出現回数を更新していきます。ペアが存在する数値の出現回数は必ず2になるため、最後にマップを走査し、出現回数が2の数値だけを取り出します。

なお、C++の std::map はキーを自動的に昇順で保持するため、結果はソート済みの順序で得られます。そのため、別途ソート処理を行う必要はありません。時間計算量は O(N log N) に抑えられ、二重ループの O(N²) よりもはるかに高速です。

まとめ

この記事では、ハッシュマップ（ハッシング技術）を使って配列内の「絶対値が同じ正負のペア」を効率的に見つける問題を解決しました。総当たり法と効率的な手法の両方の実装を C++ で示しましたが、同じロジックは C、Java、Python など他の言語でも同様に実装できます。ぜひ実際にコードを動かしてみてください。