Làm thế nào để tìm bộ ba duy nhất gần với mục tiêu đã cho bằng cách sử dụng C #?

Mô hình Two Pointers và tương tự như Triplet Sum to Zero. Chúng ta có thể làm theo một cách tiếp cận tương tự để lặp qua mảng, lấy từng số một. Ở mỗi bước, chúng tôi sẽ lưu chênh lệch giữa bộ ba và số mục tiêu, và ở mỗi bước, chúng tôi sẽ so sánh nó với chênh lệch mục tiêu tối thiểu cho đến nay, để cuối cùng, chúng tôi có thể trả về bộ ba có tổng gần nhất.

Độ phức tạp về thời gian

Sắp xếp mảng sẽ lấy O (N * logN). Nhìn chung, baSumClosest () sẽ lấy O (N * logN + N ^ 2), tiệm cận tương đương với O (N ^ 2).

Độ phức tạp về không gian

Độ phức tạp không gian của thuật toán trên sẽ là O (N) cần thiết để sắp xếp.

Ví dụ

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));
}

Đầu ra

2