সহজ পদ্ধতি হলো চারটি নেস্টেড লুপ তৈরি করে একে একে চেক করা যে চারটি এলিমেন্টের যোগফল শূন্য কিনা। যদি চারটি এলিমেন্টের যোগফল শূন্য হয়, তবে এলিমেন্টগুলো প্রিন্ট করুন।
টাইম কমপ্লেক্সিটি − O(n4)
স্পেস কমপ্লেক্সিটি − O(1)
আমরা আনঅর্ডার্ড সেট ডেটা স্ট্রাকচার ব্যবহার করতে পারি অ্যারের প্রতিটি ভ্যালু স্টোর করতে। সেট O(1) টাইমে এলিমেন্ট সার্চ করার সুবিধা দেয়। তাই অ্যারের প্রতিটি পেয়ারের জন্য, আমরা তাদের যোগফলের 네가েটিভ মান সেটে আছে কিনা চেক করব। যদি এমন এলিমেন্ট পাওয়া যায়, তবে আমরা ট্রিপলেট প্রিন্ট করতে পারি যা হবে ইন্টিজার পেয়ার এবং তাদের যোগফলের 네가েটিভ ভ্যালু।
টাইম কমপ্লেক্সিটি − O(n3)
স্পেস কমপ্লেক্সিটি − O(n)
উদাহরণ
public class Arrays{ public List<List<int>> FourSum(int[] nums){ List<List<int>> res = new List<List<int>>(); if (nums == null || nums.Length == 0){ return null; } int[] newNums = nums.OrderBy(x => x).ToArray(); for (int i = 0; i < newNums.Length; i++){ for (int j = i; j < newNums.Length; j++){ int left = j + 1; int right = newNums.Length - 1; while (left < right){ int sum = newNums[i] + newNums[j] + newNums[left] + newNums[right]; if (sum == 0){ List<int> sums = new List<int>(); sums.Add(newNums[i]); sums.Add(newNums[j]); sums.Add(newNums[left]); sums.Add(newNums[right]); res.Add(sums); int leftValue = newNums[left]; int rightValue = newNums[right]; while (left < nums.Length && leftValue == nums[left]){ left++; } while (right > left && right == nums[right]){ right--; } } else if (sum < 0){ left++; } else{ right--; } } while (j + 1 < nums.Length && nums[j] == nums[j + 1]){ j++; } } while (i + 1 < nums.Length && nums[i] == nums[i + 1]){ i++; } } return res; } } static void Main(string[] args){ Arrays s = new Arrays(); int[] nums = { 1,0,-1,0,-2,2 }; var ss = FourSum(nums); foreach (var item in ss){ foreach (var item1 in item){ Console.WriteLine(item1); } } }আউটপুট
[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
