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