C＃を使用して、指定されたターゲットに近い一意のトリプレットを見つける方法は？

Two Pointersパターンであり、Triplet SumtoZeroに似ています。同様のアプローチに従って、一度に1つの数値を取得して、配列を反復処理できます。すべてのステップで、トリプレットとターゲット数の差を保存し、各ステップでこれまでの最小ターゲット差と比較して、最終的に最も近い合計でトリプレットを返すことができるようにします。

時間計算量

配列の並べ替えにはO（N * logN）が必要です。全体として、threeSumClosest（）はO（N * logN + N ^ 2）を取ります。これは、漸近的にO（N ^ 2）と同等です。

スペースの複雑さ

上記のアルゴリズムのスペースの複雑さは、ソートに必要な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