C# ব্যবহার করে শূন্যের কাছাকাছি থাকা সমস্ত অনন্য চতুষ্পদ কিভাবে খুঁজে পাবেন?

সহজ পদ্ধতি হল আমরা চারটি নেস্টেড লুপ তৈরি করতে পারি এবং একে একে পরীক্ষা করতে পারি যে চারটি উপাদানের যোগফল শূন্য বা না। যদি চারটি উপাদানের যোগফল শূন্য হয় তবে উপাদানগুলি মুদ্রণ করুন।

সময়ের জটিলতা − O(n ⁴ )

মহাকাশের জটিলতা − O(1)

অ্যারের প্রতিটি মান সঞ্চয় করার জন্য আমরা একটি ক্রমবিহীন সেট ডেটা স্ট্রাকচার ব্যবহার করতে পারি। সেট O(1) সময়ে একটি উপাদান অনুসন্ধানের সুবিধা প্রদান করে। সুতরাং, অ্যারের প্রতিটি জোড়ার জন্য, আমরা তাদের যোগফলের ঋণাত্মক সন্ধান করব যা সেটটিতে বিদ্যমান থাকতে পারে। যদি এমন একটি উপাদান পাওয়া যায় তবে আমরা ট্রিপলেটটি প্রিন্ট করতে পারি যা হবে পূর্ণসংখ্যার জোড়া এবং তাদের যোগফলের ঋণাত্মক মান।

সময়ের জটিলতা − O(n ³ )

মহাকাশের জটিলতা − 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]]