C#을 사용하여 주어진 대상에 가까운 고유한 삼중항을 찾는 방법은 무엇입니까?

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

시간 복잡도

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