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