C++でソート済みの2つの配列からxに最も近い合計値を持つペアを見つける方法

ソート済みの2つの配列と数値 x が与えられたとき、合計が x に最も近くなるペアを見つける必要があります。このペアは、それぞれの配列から1つずつの要素を組み合わせたものです。具体的には、配列 A1[0..m-1] と A2[0..n-1]、および目標値 x が与えられ、|A1[i] + A2[j] − x| の絶対値が最小となるような A1[i] + A2[j] の組み合わせを求めます。

例えば、A1 = [1, 4, 5, 7]、A2 = [10, 20, 30, 40]、x = 32 の場合、出力は「1 と 30」になります（1 + 30 = 31 が x = 32 に最も近いため）。

アルゴリズムの考え方：双ポインタ（Two Pointer）手法

この問題は、A1 の左端から、A2 の右端からそれぞれ探索を開始し、ポインタを内側へ移動させながら解を絞り込むことで効率的に解けます。手順は以下の通りです。

• diff を初期化します。これはペアの合計と x の差を保持する変数です
• 2つのポインタ left := 0 と right := n − 1 を初期化します
• left < m かつ right >= 0 の間、以下を繰り返します
  • |A1[left] + A2[right] − x| < diff である場合
    • diff と結果（left_res、right_res）を更新します
  • A1[left] + A2[right] > x である場合
    • right を1減らします（合計を小さくするため）
  • それ以外の場合
    • left を1増やします（合計を大きくするため）
• 最後に結果を表示します

両方の配列がすでにソートされているため、この手法により全ての組み合わせを総当たりで調べることなく、線形時間で最適なペアを発見できます。計算量は O(m + n) であり、非常に効率的です。

C++での実装例

#include<iostream>
#include<cmath>
#include<climits>
using namespace std;

void findClosestPair(int A1[], int A2[], int m, int n, int x) {
    int diff = INT_MAX;
    int left_res, right_res;

    int left = 0, right = n-1;
    while (left<m && right>=0) {
        if (abs(A1[left] + A2[right] - x) < diff) {
            left_res = left;
            right_res = right;
            diff = abs(A1[left] + A2[right] - x);
        }

        if (A1[left] + A2[right] > x)
            right--;
        else
            left++;
    }

    cout << "The closest pair is [" << A1[left_res] << ", "<< A2[right_res] << "]";
}

int main() {
    int ar1[] = {1, 4, 5, 7};
    int ar2[] = {10, 20, 30, 40};

    int m = sizeof(ar1)/sizeof(ar1[0]);
    int n = sizeof(ar2)/sizeof(ar2[0]);

    int x = 32;
    findClosestPair(ar1, ar2, m, n, x);
}

出力

The closest pair is [1, 30]

まとめ

ソート済みの2つの配列から目標値に最も近い合計を持つペアを見つける問題は、双ポインタ手法を使うことで O(m + n) の計算量で解決できます。ポイントは、合計が目標値より大きければ右側のポインタを左へ移動し、小さければ左側のポインタを右へ移動することで、探索範囲を段階的に狭めていく点です。INT_MAX を使って diff を初期化することで、最初の比較が必ず成立し、正しく結果が記録される点にも注意しましょう。