Làm thế nào để tìm tất cả các bộ tứ duy nhất gần bằng 0 bằng C #?

Cách tiếp cận dễ dàng là chúng ta có thể tạo bốn vòng lặp lồng nhau và lần lượt kiểm tra xem tổng của tất cả bốn phần tử có bằng 0 hay không. Nếu tổng của bốn phần tử bằng 0 thì in các phần tử.

Độ phức tạp về thời gian - O (n ⁴ )

Độ phức tạp của không gian - O (1)

Chúng ta có thể sử dụng cấu trúc dữ liệu tập hợp không có thứ tự để lưu trữ từng giá trị của mảng. Tập hợp cung cấp lợi ích của việc tìm kiếm một phần tử trong thời gian O (1). Vì vậy, đối với mỗi cặp trong mảng, chúng ta sẽ tìm số âm của tổng của chúng có thể tồn tại trong tập hợp. Nếu một phần tử như vậy được tìm thấy thì chúng ta có thể in ra bộ ba là cặp số nguyên và giá trị âm của tổng của chúng.

Độ phức tạp về thời gian - O (n ³ )

Độ phức tạp của không gian - O (n)

Ví dụ

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

Đầu ra

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