C#을 사용하여 합이 0이 되는 모든 고유한 삼중항을 찾는 방법은 무엇입니까?

쉬운 방법은 세 개의 중첩 루프를 만들고 세 요소의 합계가 0인지 여부를 하나씩 확인할 수 있다는 것입니다. 세 요소의 합이 0이면 요소를 인쇄합니다.

시간 복잡성 - O(n ³ )

공간 복잡성 - O(1)

우리는 정렬되지 않은 집합 데이터 구조를 사용하여 배열의 각 값을 저장할 수 있습니다. Set은 O(1) 시간에 요소를 검색하는 이점을 제공합니다. 따라서 배열의 각 쌍에 대해 집합에 존재할 수 있는 합계의 음수를 찾습니다. 그러한 요소가 발견되면 정수 쌍과 그 합계의 음수 값이 될 3중항을 인쇄할 수 있습니다.

시간 복잡성 - O(n ² )

공간 복잡성 - 오(n)

예시

public class Arrays{
   public List<List<int>> ThreeSum(int[] nums){
      List<List<int>> res = new List<List<int>>();
      if (nums == null || nums.Length == 0){
         return res;
      }
      var newnums = nums.OrderBy(x => x).ToArray();
      for (int i = 0; i < newnums.Count(); i++){
         int left = i + 1;
         int right = newnums.Count() - 1;
         while (left < right){
            int sum = newnums[i] + newnums[left] + newnums[right];
            if (sum == 0){
               List<int> l = new List<int>();
               l.Add(newnums[i]);
               l.Add(newnums[left]);
               l.Add(newnums[right]);
               res.Add(l);
               int leftValue = newnums[left];
               while (left < newnums.Length && leftValue == newnums[left]){
                left++;
               }
               int riightValue = newnums[right];
               while (right > left && riightValue == newnums[right]){
                  right--;
               }
            }
            else if (sum < 0){
               left++;
            }
            else{
               right--;
            }
         }
         while (i + 1 < newnums.Length && newnums[i] == newnums[i + 1]){
            i++;
         }
      }
      return res;
   }
}

static void Main(string[] args){
   Arrays s = new Arrays();
   int[] nums = { -1, 0, 1, 2, -1, -4 };
   var ss = s.ThreeSum(nums);
   foreach (var item in ss){
      foreach (var item1 in item){
         Console.WriteLine(item1);
      }
   }
}

출력

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