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