सी # का उपयोग करके लक्ष्य के करीब चौगुनी कैसे खोजें?

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

समय की जटिलता

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