C++で2つの配列の合計を等しくする要素スワップのペアを見つける方法

要素数が異なる2つの配列があるとします。このとき、1つ目の配列に含まれる要素 x と、2つ目の配列に含まれる要素 y からなるペアを見つけます。このペアを選んで2つの配列間で要素を入れ替えた結果、両方の配列の合計が等しくなるようにするのが目的です。

例として、配列 A が [4, 1, 2, 2, 1, 1]、配列 B が [3, 3, 6, 3] を持っている場合を考えてみましょう。A の合計は 11、B の合計は 15 です。ここで (1, 3) というペアを選び、これらの値を2つの配列間で入れ替えると、合計は次のようになります。

• A: [4, 3, 2, 2, 1, 1] → 合計 13
• B: [1, 3, 6, 3] → 合計 13

両者の合計が一致し、条件を満たすことがわかります。

解法のアプローチ

最もシンプルな方法は、全ての要素の組み合わせ（ペア）を総当たりで調べることです。各ペアについて、実際に入れ替えた場合の新しい合計を計算し、両者が等しくなるかどうかを判定します。

なお、数学的に考えると、2つの配列の合計の差を d = sum_A − sum_B としたとき、A[i] − B[j] = d / 2 を満たすペアを探せばよいことになります。そのため、差 d が奇数である場合は解が存在しないことにも注意してください。

C++での実装例

#include<iostream>
using namespace std;

int arraySum(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
    return sum;
}

void getPair(int A[], int n, int B[], int m) {
    int sum_first = arraySum(A, n);
    int sum_second = arraySum(B, m);
    int newsum_first, newsum_second;
    int first = -1, second = -1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            newsum_first = sum_first - A[i] + B[j];
            newsum_second = sum_second - B[j] + A[i];
            if (newsum_first == newsum_second) {
                first = A[i];
                second = B[j];
            }
        }
    }

    if (first != -1)
        cout << "(" << first << ", " << second << ")";
    else
        cout << "条件を満たすペアは存在しません";
}

int main() {
    int A[] = { 4, 1, 2, 2, 1, 1 };
    int n = sizeof(A) / sizeof(A[0]);
    int B[] = { 3, 3, 6, 3 };
    int m = sizeof(B) / sizeof(B[0]);

    getPair(A, n, B, m);
    return 0;
}

出力結果

(1, 3)

計算量と改善のポイント

上記の実装では、二重ループによってすべてのペアを確認しているため、時間計算量は O(n × m) となります。また、元のコードではペアが見つからなかった場合に出力変数が未初期化のままになるという問題がありましたが、今回は初期値 -1 を設定し、見つからなかった場合のメッセージ表示も追加することで安全性を高めています。

さらに効率化したい場合は、片方の配列の要素をハッシュセット（unordered_set）に格納しておき、もう片方の各要素に対して「必要な値」が存在するかを O(1) で照会する方法があります。これにより、全体の時間計算量を O(n + m) まで削減できます。