Làm thế nào để tìm phần tư gần với mục tiêu bằng cách sử dụng C #?

Mô hình hai con trỏ và tương tự như tổng gấp bốn lần Tổng đến 0. 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 sự khác biệt giữa bộ bốn và số đích, 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 với 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). Tổng thể bốnSumClosest () sẽ lấy O (N * logN + N ^ 3), tiệm cận tương đương với O (N ^ 3).

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

Đầu ra

0