C#でターゲットに最も近い一意のトリプレット（3つの数の合計）を見つける方法

この問題は「Two Pointers（双方向ポインタ）」パターンを用いて解くことができ、「Triplet Sum to Zero（合計がゼロになるトリプレット）」の問題とよく似ています。基本的なアプローチとしては、配列をソートした上で、1つの要素を固定しながら残りの2つの要素をポインタで探索していきます。

各ステップでは、現在のトリプレットの合計とターゲット値との差を記録し、それまでに見つかった最小の差と比較します。これにより、探索が終わった時点で、ターゲットに最も近い合計を持つトリプレットを返すことができます。

計算量

時間計算量

配列のソートには O(N * logN) かかります。全体の ThreeSumClosest() の処理は O(N * logN + N²) となり、漸近的には O(N²) と同等です。

空間計算量

このアルゴリズムの空間計算量は O(N) で、これはソートに必要な分です。

実装例

public class Arrays{
   public int ThreeSumClosest(int[] num, int target){
      if (num == null || num.Length == 0){
         return -1;
      }
      int[] nums = num.OrderBy(x => x).ToArray();
      int initialclosest = nums[0] + nums[1] + nums[2];
      for (int i = 0; i < nums.Count(); i++){
         int left = i + 1;
         int right = nums.Length - 1;
         while (left < right){
            int newClosest = nums[i] + nums[left] + nums[right];
            if (Math.Abs(newClosest - target) < Math.Abs(initialclosest - target)){
               initialclosest = newClosest;
            }
            if (newClosest == target){
               return newClosest;
            }
            else if (newClosest < target){
               left++;
            }
            else
            {
               right--;
            }
         }
      }
      return initialclosest;
   }
}

static void Main(string[] args){
   Arrays s = new Arrays();
   int[] nums = { -1, 2, 1, -4 };
   Console.WriteLine(s.ThreeSumClosest(nums, 1));
}

出力結果

2

この例では、入力配列 { -1, 2, 1, -4 } に対してターゲット値 1 を指定しています。-1 + 2 + 1 = 2 がターゲットに最も近い合計となるため、結果として 2 が出力されます。