如何使用 C# 找到所有接近于零的唯一四元组？

Z时代
2024-01-10
分类：综合

简单的方法是我们可以创建四个嵌套循环并一一检查所有四个元素的总和是否为零。如果四个元素的总和为零，则打印元素。

时间复杂度- O(n ⁴ )

空间复杂度- O(1)

我们可以使用无序集合数据结构来存储数组的每个值。Set 提供了在 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);
      }
   }
}