सी # का उपयोग करके दिए गए लक्ष्य के करीब अद्वितीय ट्रिपल कैसे खोजें?

दो पॉइंटर्स पैटर्न और ट्रिपल सम टू जीरो के समान है। हम एक समय में एक नंबर लेते हुए, सरणी के माध्यम से पुनरावृति करने के लिए एक समान दृष्टिकोण का पालन कर सकते हैं। हर कदम पर, हम ट्रिपलेट और लक्ष्य संख्या के बीच के अंतर को बचाएंगे, और प्रत्येक चरण में हम इसकी तुलना अब तक के न्यूनतम लक्ष्य अंतर से करेंगे, ताकि अंत में, हम ट्रिपलेट को निकटतम योग के साथ वापस कर सकें।

समय की जटिलता

सरणी को छाँटने पर 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