টু পয়েন্টার প্যাটার্ন এবং ট্রিপলেট সম টু জিরোর সাথে মিলতুল্য। আমরা একই পদ্ধতিতে অ্যারে ইটারেট করতে পারি, একবারে একটি নম্বর নিয়ে। প্রতিটি ধাপে, ট্রিপলেট এবং টার্গেট নম্বরের পার্থক্য সংরক্ষণ করব এবং প্রতিটি ধাপে এটিকে 지금까지 के ন্যূনতম টার্গেট পার্থক্যের সাথে তুলনা করব, যাতে শেষে সবচেয়ে নিকটস্থ সমের ট্রিপলেট রিটার্ন করা যায়।
টাইম কমপ্লেক্সিটি
অ্যারে সর্ট করতে 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
