Comment trouver tous les quadruples uniques proches de zéro en utilisant C# ?

Le moyen le plus simple est de créer quatre boucles imbriquées et de vérifier une par une si la somme des quatre éléments est nulle. Si la somme des quatre éléments est nulle, imprimez les éléments.

Complexité temporelle - O(n⁴)

- O(1)

Nous pouvons utiliser une structure de données d'ensemble non ordonnée pour stocker chaque valeur du tableau. Set offre l'avantage de rechercher des éléments en un temps O(1). Ainsi, pour chaque paire du tableau, nous chercherons la valeur négative de leur somme qui peut exister dans l'ensemble. Si un tel élément est trouvé alors nous pouvons imprimer un triplet qui sera une paire d'entiers et la valeur négative de leur somme.

Complexité temporelle - O(n ³)

Complexité spatiale - O(n)

Exemple

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);
      }
   }
}

Sortie

[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!