C#을 사용하여 대상에 가까운 사중항을 찾는 방법은 무엇입니까?

Two Pointers 패턴이며 4중 Sum to Zero와 유사합니다. 한 번에 하나의 숫자를 사용하여 배열을 반복하는 유사한 접근 방식을 따를 수 있습니다. 매 단계마다 quadrulet과 target number의 차이를 저장하고, 각 단계에서 지금까지의 최소 target 차이와 비교하여 결국 가장 가까운 합으로 triplet을 반환할 수 있습니다.

시간 복잡도

배열을 정렬하려면 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