C＃を使用してターゲットに近い4つ組を見つける方法は？

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

時間計算量

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

スペースの複雑さ

上記のアルゴリズムのスペースの複雑さは、ソートに必要なO（N）になります。

例

public class Arrays{
   public int FourSumClosestToTarget(int[] nums, int target){
      if (nums == null || nums.Length == 0){
         return -1;
      }
      int[] newNums = nums.OrderBy(x => x).ToArray();
      int initialSum = newNums[0] + newNums[1] + newNums[2] + newNums[3];
      for (int i = 0; i < nums.Length; i++){
         for (int j = i; j < nums.Length; j++){
            int left = j + 1;
            int right = nums.Length - 1;
            while (left < right){
               int nearestSum = newNums[i] + newNums[j] + newNums[left] + newNums[right];
               if (nearestSum < initialSum){
                  initialSum = nearestSum;
               }
               if (nearestSum == target){
                  return nearestSum;
               }
               else if (nearestSum < target){
                  left++;
               }
               else{
                  right--;
               }
            }
         }
      }
     return initialSum;
   }
}

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

出力

0