दो पॉइंटर्स पैटर्न और चौगुनी योग शून्य के समान है। हम सरणी के माध्यम से पुनरावृति करने के लिए एक समान दृष्टिकोण का पालन कर सकते हैं, एक समय में एक संख्या लेते हुए। प्रत्येक चरण में, हम चौगुनी और लक्ष्य संख्या के बीच का अंतर सहेजेंगे, और प्रत्येक चरण में हम अब तक के न्यूनतम लक्ष्य अंतर के साथ इसकी तुलना करेंगे, ताकि अंत में, हम निकटतम योग वाली तिकड़ी को लौटा सकें।
समय जटिलता
सरणी को सॉर्ट करने में 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
