【Java】2つのソート済み配列から最も近いペアを見つけるプログラムの書き方

2つのソート済み配列が与えられたとき、それぞれの配列から1要素ずつ選んだペアのうち、合計が指定した目標値に最も近くなる組み合わせを見つける問題は、アルゴリズム学習における定番テーマの一つです。本記事では、効率的なツーポインタ（二重走査）手法を用いたJavaプログラムを紹介します。

サンプルコード

import java.util.Arrays;

public class Demo {
   void closest_pair(int my_arr_1[], int my_arr_2[], int sum){
      // ツーポインタ手法は配列がソート済みであることが前提のため、先にソートする
      Arrays.sort(my_arr_1);
      Arrays.sort(my_arr_2);

      int diff = Integer.MAX_VALUE;    // 目標値との最小の差
      int result_l = 0, result_r = 0;  // 最適なペアのインデックス
      int l = 0, r = my_arr_2.length - 1;

      while (l < my_arr_1.length && r >= 0){
         int current_diff = Math.abs(my_arr_1[l] + my_arr_2[r] - sum);
         if (current_diff < diff){
            result_l = l;
            result_r = r;
            diff = current_diff;
         }
         if (my_arr_1[l] + my_arr_2[r] > sum)
            r--;   // 合計が大きすぎるため、配列2側の値を小さくする
         else
            l++;   // 合計が小さすぎるため、配列1側の値を大きくする
      }
      System.out.print("合計が " + sum + " に最も近いペアは ["
         + my_arr_1[result_l] + ", " + my_arr_2[result_r] + "] です");
   }
   public static void main(String args[]){
      Demo my_ob = new Demo();
      int my_arr_1[] = {56, 78, 99, 11};
      int my_arr_2[] = {33, 12, 69, 87};
      int val = 79;
      my_ob.closest_pair(my_arr_1, my_arr_2, val);
   }
}

実行結果

合計が 79 に最も近いペアは [11, 69] です

この例では、配列1から「11」、配列2から「69」を選んだときの合計が「80」となり、目標値「79」との差がわずか1と、すべての組み合わせの中で最も小さくなります。

コードの解説

Demoクラスには、2つの配列と目標値を受け取るclosest_pairメソッドが定義されています。まずArrays.sort()で両方の配列を昇順に並べ替えます。これは、後述するツーポインタ手法が「配列がソート済みであること」を前提としているためです。

続いて、左ポインタlを配列1の先頭に、右ポインタrを配列2の末尾に設定し、次の手順で走査を進めます。

1. 現在のペアの合計と目標値の差の絶対値を計算し、これまでの最小差より小さければ、そのインデックスと差を記録する。
2. 合計が目標値より大きい場合は、合計を減らすために右ポインタを1つ左へ移動する。
3. 合計が目標値以下の場合は、合計を増やすために左ポインタを1つ右へ移動する。

どちらかのポインタが範囲外に出るとループは終了し、記録しておいたインデックスの要素が「最も近いペア」として確定します。mainメソッドでは、Demoクラスのインスタンスを生成し、2つの整数配列と目標値79を渡してメソッドを呼び出し、結果をコンソールに出力しています。

なぜツーポインタで正しく求まるのか

両配列がソート済みであれば、「合計が目標値より大きいのに配列1の値をさらに大きくしても意味がない」「合計が目標値より小さいのに配列2の値をさらに小さくしても意味がない」という性質が成り立ちます。この性質により、答えになり得ない組み合わせを一括して除外できるため、全ペアを総当たりせずとも最適解にたどり着けます。

計算量

ソートにO(n log n)、走査にO(n + m)かかるため、全体の時間計算量はO(n log n + m log m)です。もし配列が最初からソート済みであれば、ソート処理を省略でき、O(n + m)の線形時間で解けます。全ペアを調べる総当たり方式のO(n × m)と比べ、データ量が多いほど大きな差がつきます。