배열의 삼중합(3SUM) - TECHCODEVIEW.COM

배열이 주어지면 도착[] 크기의 N 그리고 정수 엑스 . 주어진 정수로 합산되는 삼중항이 배열에 있는지 찾아보세요. 엑스 .

예:

숨겨진 앱을 공개하는 방법

입력: 배열 = {12, 3, 4, 1, 6, 9}, 합계 = 24;
산출: 12, 3, 9
설명: 삼중항(12, 3, 9)이 존재합니다.
합계가 24인 배열에 있습니다.

입력: 배열 = {1, 2, 3, 4, 5}, 합계 = 9
산출: 5, 3, 1
설명: 삼중항(5, 3, 1)이 존재합니다.
합이 9인 배열에서

권장되는 배열의 삼중항 합산 연습해 보세요!

배열의 삼중합(3sum) 모든 삼중항을 생성하여:

간단한 방법은 가능한 모든 삼중항을 생성하고 모든 삼중항의 합을 주어진 값과 비교하는 것입니다. 다음 코드는 세 개의 중첩 루프를 사용하여 이 간단한 메서드를 구현합니다.

단계별 접근 방식:

주어진 길이의 배열 N 그리고 합계 에스
3개의 중첩 루프를 만듭니다. 첫 번째 루프는 처음부터 끝까지 실행되고(루프 카운터 i), 두 번째 루프는 다음에서 실행됩니다. 나+1 끝까지 (루프 카운터 j) 세 번째 루프는 다음에서 실행됩니다. j+1 끝까지 (루프 카운터 k)
이 루프의 카운터는 다음의 인덱스를 나타냅니다. 삼 삼중 요소.
i번째, j번째, k번째 요소의 합을 구합니다. 합계가 주어진 합계와 같은 경우. 삼중항을 인쇄하고 중단하세요.
삼중항이 없으면 삼중항이 존재하지 않는다고 인쇄하세요.

다음은 위의 접근 방식을 구현한 것입니다.

C++

#include> using> namespace> std;> // returns true if there is triplet with sum equal> // to 'sum' present in A[]. Also, prints the triplet> bool> find3Numbers(>int> A[],>int> arr_size,>int> sum)> {> >// Fix the first element as A[i]> >for> (>int>

i = 0; i   {   // Fix the second element as A[j]   for (int j = i + 1; j   {   // Now look for the third number   for (int k = j + 1; k   {   if (A[i] + A[j] + A[k] == sum)  {   cout << 'Triplet is ' << A[i] <<  ', ' << A[j] << ', ' << A[k];   return true;   }   }   }   }   // If we reach here, then no triplet was found   return false;  }  /* Driver code */ int main()  {   int A[] = { 1, 4, 45, 6, 10, 8 };   int sum = 22;   int arr_size = sizeof(A) / sizeof(A[0]);   find3Numbers(A, arr_size, sum);   return 0;  }  // This is code is contributed by rathbhupendra>

씨

#include> // returns true if there is triplet with sum equal> // to 'sum' present in A[]. Also, prints the triplet> bool> find3Numbers(>int> A[],>int> arr_size,>int> sum)> {> >int> l, r;> >// Fix the first element as A[i]> >for> (>int>

i = 0; i   // Fix the second element as A[j]  for (int j = i + 1; j   // Now look for the third number  for (int k = j + 1; k   if (A[i] + A[j] + A[k] == sum) {  printf('Triplet is %d, %d, %d',  A[i], A[j], A[k]);  return true;  }  }  }  }  // If we reach here, then no triplet was found  return false; } /* Driver program to test above function */ int main() {  int A[] = { 1, 4, 45, 6, 10, 8 };  int sum = 22;  int arr_size = sizeof(A) / sizeof(A[0]);  find3Numbers(A, arr_size, sum);  return 0; }>

자바

// Java program to find a triplet> class> FindTriplet {> >// returns true if there is triplet with sum equal> >// to 'sum' present in A[]. Also, prints the triplet> >boolean> find3Numbers(>int> A[],>int> arr_size,>int> sum)> >{> >int> l, r;> >// Fix the first element as A[i]> >for> (>int> i =>0>

; i 2; i++) {  // Fix the second element as A[j]  for (int j = i + 1; j 1; j++) {  // Now look for the third number  for (int k = j + 1; k   if (A[i] + A[j] + A[k] == sum) {  System.out.print('Triplet is ' + A[i] + ', ' + A[j] + ', ' + A[k]);  return true;  }  }  }  }  // If we reach here, then no triplet was found  return false;  }  // Driver program to test above functions  public static void main(String[] args)  {  FindTriplet triplet = new FindTriplet();  int A[] = { 1, 4, 45, 6, 10, 8 };  int sum = 22;  int arr_size = A.length;  triplet.find3Numbers(A, arr_size, sum);  } }>

파이썬3

# Python3 program to find a triplet> # that sum to a given value> # returns true if there is triplet with> # sum equal to 'sum' present in A[].> # Also, prints the triplet> def> find3Numbers(A, arr_size,>sum>):> ># Fix the first element as A[i]> >for> i>in> range>(>0>, arr_size>->2>):> ># Fix the second element as A[j]> >for> j>in> range>(i>+> 1>, arr_size>->1>):> > ># Now look for the third number> >for> k>in> range>(j>+> 1>, arr_size):> >if> A[i]>+> A[j]>+> A[k]>=>=> sum>:> >print>(>'Triplet is'>, A[i],> >', '>, A[j],>', '>, A[k])> >return> True> > ># If we reach here, then no> ># triplet was found> >return> False> # Driver program to test above function> A>=> [>1>,>4>,>45>,>6>,>10>,>8>]> sum> => 22> arr_size>=> len>(A)> find3Numbers(A, arr_size,>sum>)> # This code is contributed by Smitha Dinesh Semwal>

씨#

// C# program to find a triplet> // that sum to a given value> using> System;> class> GFG {> >// returns true if there is> >// triplet with sum equal> >// to 'sum' present in A[].> >// Also, prints the triplet> >static> bool> find3Numbers(>int>[] A,> >int> arr_size,> >int> sum)> >{> >// Fix the first> >// element as A[i]> >for> (>int> i = 0;> >

i   // Fix the second  // element as A[j]  for (int j = i + 1;  j   // Now look for  // the third number  for (int k = j + 1;  k   if (A[i] + A[j] + A[k] == sum) {  Console.WriteLine('Triplet is ' + A[i] + ', ' + A[j] + ', ' + A[k]);  return true;  }  }  }  }  // If we reach here,  // then no triplet was found  return false;  }  // Driver Code  static public void Main()  {  int[] A = { 1, 4, 45, 6, 10, 8 };  int sum = 22;  int arr_size = A.Length;  find3Numbers(A, arr_size, sum);  } } // This code is contributed by m_kit>

자바스크립트

마이리버켓

> // Javascript program to find a triplet> // returns true if there is triplet with sum equal> // to 'sum' present in A[]. Also, prints the triplet> function> find3Numbers(A, arr_size, sum)> {> >let l, r;> >// Fix the first element as A[i]> >for>

(let i = 0; i   {   // Fix the second element as A[j]   for (let j = i + 1; j   {   // Now look for the third number   for (let k = j + 1; k   {   if (A[i] + A[j] + A[k] == sum)   {   document.write('Triplet is ' + A[i] +   ', ' + A[j] + ', ' + A[k]);   return true;   }   }   }   }   // If we reach here, then no triplet was found   return false;  }  /* Driver code */    let A = [ 1, 4, 45, 6, 10, 8 ];   let sum = 22;   let arr_size = A.length;   find3Numbers(A, arr_size, sum);    // This code is contributed by Mayank Tyagi>

PHP

 // PHP program to find a triplet  // that sum to a given value // returns true if there is  // triplet with sum equal to // 'sum' present in A[]. // Also, prints the triplet function find3Numbers($A, $arr_size, $sum) {  $l; $r;  // Fix the first  // element as A[i]  for ($i = 0;   $i <$arr_size - 2; $i++)  {  // Fix the second   // element as A[j]  for ($j = $i + 1;   $j <$arr_size - 1; $j++)  {  // Now look for the  // third number  for ($k = $j + 1;   $k <$arr_size; $k++)  {  if ($A[$i] + $A[$j] +   $A[$k] == $sum)  {  echo 'Triplet is', ' ', $A[$i],  ', ', $A[$j],   ', ', $A[$k];  return true;  }  }  }  }  // If we reach here, then  // no triplet was found  return false; } // Driver Code $A = array(1, 4, 45,   6, 10, 8); $sum = 22; $arr_size = sizeof($A); find3Numbers($A, $arr_size, $sum); // This code is contributed by ajit ?>>

산출

Triplet is 4, 10, 8>

복잡성 분석:

시간 복잡도: 에^삼), 배열을 순회하는 세 개의 중첩 루프가 있으므로 시간 복잡도는 O(n^3)입니다.
보조 공간: O(1), 추가 공간이 필요하지 않습니다.

배열의 삼중합(3sum) 사용하여 두 포인터 기술 :

배열을 정렬하면 알고리즘의 효율성이 향상될 수 있습니다. 이 효율적인 접근 방식은 다음을 사용합니다. 두 포인터 기술 . 배열을 순회하고 삼중항의 첫 번째 요소를 수정합니다. 이제 두 포인터 알고리즘을 사용하여 합이 다음과 같은 쌍이 있는지 찾습니다. x – 배열[i] . 두 포인터 알고리즘은 선형 시간이 걸리므로 중첩 루프보다 낫습니다.

단계별 접근 방식:

주어진 배열을 정렬합니다.
배열을 반복하고 가능한 삼중항의 첫 번째 요소를 수정합니다. 도착[i] .
그런 다음 두 개의 포인터를 수정합니다. 나는 + 1 그리고 다른 하나는 엔 - 1 . 그리고 합계를 보면,
- 합계가 필요한 합계보다 작으면 첫 번째 포인터를 증가시킵니다.
- 그렇지 않으면 합계가 더 큰 경우 종료 포인터를 줄여 합계를 줄입니다.
- 그렇지 않고 두 포인터의 요소 합이 주어진 합과 같으면 삼중항을 인쇄하고 중단합니다.

다음은 위의 접근 방식을 구현한 것입니다.

C++

// C++ program to find a triplet> #include> using> namespace> std;> // returns true if there is triplet with sum equal> // to 'sum' present in A[]. Also, prints the triplet> bool> find3Numbers(>int> A[],>int> arr_size,>int> sum)> {> >int> l, r;> >/* Sort the elements */> >sort(A, A + arr_size);> >/* Now fix the first element one by one and find the> >other two elements */> >for> (>int>

i = 0; i   // To find the other two elements, start two index  // variables from two corners of the array and move  // them toward each other  l = i + 1; // index of the first element in the  // remaining elements  r = arr_size - 1; // index of the last element  while (l   if (A[i] + A[l] + A[r] == sum) {  printf('Triplet is %d, %d, %d', A[i], A[l],A[r]);  return true;  }  else if (A[i] + A[l] + A[r]   l++;  else // A[i] + A[l] + A[r]>합계 r--;  } } // 여기에 도달하면 세 쌍이 발견되지 않은 것입니다. return false; } /* 위 함수를 테스트하기 위한 드라이버 프로그램 */ int main() { int A[] = { 1, 4, 45, 6, 10, 8 };  정수 합계 = 22;  int arr_size = sizeof(A) / sizeof(A[0]);  find3Numbers(A, arr_size, sum);  0을 반환합니다. } // 이 코드는 Aditya Kumar(adityakumar129)가 제공한 것입니다.>

씨

// C program to find a triplet> #include> #include> #include> int> cmpfunc(>const> void>* a,>const> void>* b)> {> >return> (*(>int>*)a - *(>int>*)b);> }> // returns true if there is triplet with sum equal> // to 'sum' present in A[]. Also, prints the triplet> bool> find3Numbers(>int> A[],>int> arr_size,>int> sum)> {> >int> l, r;> > >/* Sort the elements */> >qsort>(A, arr_size,>sizeof>(>int>), cmpfunc);> > >/* Now fix the first element one by one and find the> >other two elements */> >for> (>int>

i = 0; i   {    // To find the other two elements, start two index  // variables from two corners of the array and move  // them toward each other  l = i + 1; // index of the first element in the  // remaining elements  r = arr_size - 1; // index of the last element  while (l   if (A[i] + A[l] + A[r] == sum) {  printf('Triplet is %d, %d, %d', A[i], A[l],  A[r]);  return true;  }  else if (A[i] + A[l] + A[r]   l++;  else // A[i] + A[l] + A[r]>합계 r--;  } } // 여기에 도달하면 세 쌍이 발견되지 않은 것입니다. return false; } /* 위 함수를 테스트하기 위한 드라이버 프로그램 */ int main() { int A[] = { 1, 4, 45, 6, 10, 8 };  정수 합계 = 22;  int arr_size = sizeof(A) / sizeof(A[0]);  find3Numbers(A, arr_size, sum);  0을 반환합니다. } // 이 코드는 Aditya Kumar(adityakumar129)가 제공한 것입니다.>

자바

// Java program to find a triplet> class> FindTriplet {> >// returns true if there is triplet with sum equal> >// to 'sum' present in A[]. Also, prints the triplet> >boolean> find3Numbers(>int> A[],>int> arr_size,>int> sum)> >{> >int> l, r;> >/* Sort the elements */> >quickSort(A,>0>, arr_size ->1>);> >/* Now fix the first element one by one and find the> >other two elements */> >for> (>int> i =>0>

; i 2; i++) {  // To find the other two elements, start two  // index variables from two corners of the array  // and move them toward each other  l = i + 1; // index of the first element in the  // remaining elements  r = arr_size - 1; // index of the last element  while (l   if (A[i] + A[l] + A[r] == sum) {  System.out.print('Triplet is ' + A[i] + ', ' + A[l] + ', ' + A[r]);  return true;  }  else if (A[i] + A[l] + A[r]   l++;  else // A[i] + A[l] + A[r]>합계 r--;  } } // 여기에 도달하면 세 쌍이 발견되지 않은 것입니다. return false;  } int partition(int A[], int si, int ei) { int x = A[ei];  int i = (si - 1);  int j;  (j = si; j<= ei - 1; j++) {  if (A[j] <= x) {  i++;  int temp = A[i];  A[i] = A[j];  A[j] = temp;  }  }  int temp = A[i + 1];  A[i + 1] = A[ei];  A[ei] = temp;  return (i + 1);  }  /* Implementation of Quick Sort  A[] -->정렬할 배열 si --> 시작 인덱스 ei --> 끝 인덱스 */ void QuickSort(int A[], int si, int ei) { int pi;  /* 파티셔닝 인덱스 */ if (si pi = partition(A, si, ei); QuickSort(A, si, pi - 1); QuickSort(A, pi + 1, ei); } } // 테스트할 드라이버 프로그램 위 함수 public static void main(String[] args) { FindTriplet 삼중항 = new FindTriplet(); int A[] = { 1, 4, 45, 6, 10, 8 } int arr_size = A. 길이; 삼중항.find3Numbers(A, arr_size, sum) } }>

파이썬3

# Python3 program to find a triplet> # returns true if there is triplet> # with sum equal to 'sum' present> # in A[]. Also, prints the triplet> def> find3Numbers(A, arr_size,>sum>):> ># Sort the elements> >A.sort()> ># Now fix the first element> ># one by one and find the> ># other two elements> >for> i>in> range>(>0>, arr_size>->2>):> > ># To find the other two elements,> ># start two index variables from> ># two corners of the array and> ># move them toward each other> > ># index of the first element> ># in the remaining elements> >l>=> i>+> 1> > ># index of the last element> >r>=> arr_size>->1> >while>

(l     if( A[i] + A[l] + A[r] == sum):  print('Triplet is', A[i],   ', ', A[l], ', ', A[r]);  return True    elif (A[i] + A[l] + A[r] sum r -= 1 # 여기에 도달하면 # 삼중 항을 찾지 못한 것입니다. return False # 위 함수를 테스트하기 위한 드라이버 프로그램 A = [1, 4, 45, 6, 10, 8] sum = 22 arr_size = len(A) find3Numbers(A, arr_size, sum) # 이 내용은 Smitha Dinesh Semwal이 기여했습니다.>

numpy 린스페이스

씨#

// C# program to find a triplet> using> System;> class> GFG {> >// returns true if there is triplet> >// with sum equal to 'sum' present> >// in A[]. Also, prints the triplet> >bool> find3Numbers(>int>[] A,>int> arr_size,> >int> sum)> >{> >int> l, r;> >/* Sort the elements */> >quickSort(A, 0, arr_size - 1);> >/* Now fix the first element> >one by one and find the> >other two elements */> >for> (>int>

i = 0; i   // To find the other two elements,  // start two index variables from  // two corners of the array and  // move them toward each other  l = i + 1; // index of the first element  // in the remaining elements  r = arr_size - 1; // index of the last element  while (l   if (A[i] + A[l] + A[r] == sum) {  Console.Write('Triplet is ' + A[i] + ', ' + A[l] + ', ' + A[r]);  return true;  }  else if (A[i] + A[l] + A[r]   l++;  else // A[i] + A[l] + A[r]>합계 r--;  } } // 여기에 도달하면 // 삼중항을 찾을 수 없는 것입니다. return false;  } int partition(int[] A, int si, int ei) { int x = A[ei];  int i = (si - 1);  int j;  (j = si; j<= ei - 1; j++) {  if (A[j] <= x) {  i++;  int temp = A[i];  A[i] = A[j];  A[j] = temp;  }  }  int temp1 = A[i + 1];  A[i + 1] = A[ei];  A[ei] = temp1;  return (i + 1);  }  /* Implementation of Quick Sort A[] -->정렬할 배열 si --> 시작 인덱스 ei --> 끝 인덱스 */ void QuickSort(int[] A, int si, int ei) { int pi;  /* 파티셔닝 인덱스 */ if (si pi = partition(A, si, ei); QuickSort(A, si, pi - 1); QuickSort(A, pi + 1, ei); } } // 드라이버 코드 static void Main() { GFG 삼중항 = new GFG(); int[] A = new int[] { 1, 4, 45, 6, 10, 8 }; int arr_size = A.Length; (A, arr_size, sum); } } // 이 코드는 mits에서 제공한 것입니다.>

자바스크립트

(let i = 0; i   // To find the other two  // elements, start two index  // variables from two corners of   // the array and move  // them toward each other    // index of the first element in the  l = i + 1;     // remaining elements    // index of the last element  r = arr_size - 1;   while (l   if (A[i] + A[l] + A[r] == sum)   {  document.write('Triplet is ' + A[i] + ', '  + A[l] + ', ' + A[r]);  return true;  }  else if (A[i] + A[l] + A[r]   l++;  else // A[i] + A[l] + A[r]>합계 r--;  } } // 여기에 도달하면 세 쌍이 발견되지 않은 것입니다. return false; } /* 위 기능을 테스트하기 위한 드라이버 프로그램 */ let A = [ 1, 4, 45, 6, 10, 8 ];  합계 = 22라고 가정합니다.  arr_size = A.length;  find3Numbers(A, arr_size, sum); // 이 코드는 Mayank Tyagi가 제공한 것입니다.>

PHP

 // PHP program to find a triplet // returns true if there is  // triplet with sum equal to // 'sum' present in A[]. Also, // prints the triplet function find3Numbers($A, $arr_size, $sum) {  $l; $r;  /* Sort the elements */  sort($A);  /* Now fix the first element   one by one and find the  other two elements */  for ($i = 0; $i <$arr_size - 2; $i++)   {  // To find the other two elements,   // start two index variables from   // two corners of the array and   // move them toward each other  $l = $i + 1; // index of the first element   // in the remaining elements  // index of the last element  $r = $arr_size - 1;   while ($l <$r)   {  if ($A[$i] + $A[$l] +   $A[$r] == $sum)  {  echo 'Triplet is ', $A[$i], ' ',  $A[$l], ' ',   $A[$r], '
';  return true;  }  else if ($A[$i] + $A[$l] +  $A[$r] <$sum)  $l++;  else // A[i] + A[l] + A[r]>합계 $r--;  } } // 여기에 도달하면 // 삼중항을 찾을 수 없는 것입니다. return false; } // 드라이버 코드 $A = 배열(1, 4, 45, 6, 10, 8); $합계 = 22; $arr_size = sizeof($A); find3Numbers($A, $arr_size, $sum); // 이 코드는 ajit가 제공한 것입니다. ?>>

산출

Triplet is 4, 8, 10>

복잡성 분석:

시간 복잡도: O(N^2), 배열을 순회하는 중첩 루프가 두 개뿐이므로 시간 복잡도는 O(n^2)입니다. 두 포인터 알고리즘은 O(n) 시간이 걸리며 첫 번째 요소는 다른 중첩 순회를 사용하여 수정될 수 있습니다.
보조 공간: O(1), 추가 공간이 필요하지 않습니다.

배열의 삼중합(3sum) 사용하여 해싱 :

이 접근 방식은 추가 공간을 사용하지만 두 포인터 접근 방식보다 간단합니다. 두 개의 루프 외부 루프를 처음부터 끝까지 실행하고 내부 루프를 다음에서 실행합니다. 나+1 끝으로. 해시맵을 생성하거나 그 사이에 요소를 저장하도록 설정 나+1 에게 n-1 . 따라서 주어진 합계가 엑스, 세트에 다음과 같은 숫자가 있는지 확인하십시오. 엑스 – 도착[i] – 도착[j] . 그렇다면 삼중항을 인쇄합니다.

단계별 접근 방식:

배열을 반복하여 첫 번째 요소( 일체 포함] ) 삼중항의 경우.
각각 일체 포함] , 해시맵을 사용하세요 원하는 합계를 완성하는 잠재적인 두 번째 요소를 저장합니다. (합 – A[i]) .
중첩 루프 내에서 현재 요소( A[j] ) 및 원하는 합계( 합 – A[i] )이 해시맵에 존재합니다. 그렇다면 삼중 항을 찾은 다음 인쇄하십시오.
전체 배열에서 삼중항이 발견되지 않으면 함수는 다음을 반환합니다. 거짓 .

다음은 위의 접근 방식을 구현한 것입니다.

C++

#include> using> namespace> std;> // Function to find a triplet with a given sum in an array> bool> find3Numbers(>int> A[],>int> arr_size,>int> sum)> {> >// Fix the first element as A[i]> >for> (>int>

i = 0; i   // Create a set to store potential second elements  // that complement the desired sum  unordered_set 에스;  // 목표 합계에 도달하는 데 필요한 // 현재 합계를 계산합니다. int curr_sum = sum - A[i];  // 하위 배열 A[i+1..n-1]을 반복하여 // 필요한 합계가 있는 쌍을 찾습니다. for (int j = i + 1; j // 두 번째 요소 int에 필요한 // 값 계산 필수_값 = curr_sum - A[j]; // 필요한 값이 설정되어 있는지 확인합니다. if (s.find(required_value) != s.end()) { // 삼중항이 발견되었습니다. / 요소 printf('Triplet is %d, %d, %d', A[i], A[j], 필수_값) return true } // 미래를 위해 현재 요소를 세트에 추가합니다. checks s.insert(A[j]); } } // 트리플렛이 발견되지 않으면 false를 반환합니다. return false } /* 위 함수를 테스트하기 위한 드라이버 프로그램 */ int main() { int A[] = { 1, 4, 45, 6, 10, 8 }; int sum = 22; int arr_size = sizeof(A) / sizeof(A[0]); // 트리플렛이 있는 경우 찾아서 인쇄합니다. find3Numbers(A, arr_size, sum); 0을 반환합니다.>

자바

import> java.util.HashSet;> public> class> TripletSumFinder {> >// Function to find a triplet with a given sum in an> >// array> >public> static> boolean> >find3Numbers(>int>[] A,>int> arr_size,>int> sum)> >{> >// Fix the first element as A[i]> >for> (>int> i =>0>

; i 2; i++) {  // Create a HashSet to store potential second  // elements that complement the desired sum  HashSet s = new HashSet();  // Calculate the current sum needed to reach the  // target sum  int curr_sum = sum - A[i];  // Iterate through the subarray A[i+1..n-1] to  // find a pair with the required sum  for (int j = i + 1; j   // Calculate the required value for the  // second element  int required_value = curr_sum - A[j];  // Check if the required value is present in  // the HashSet  if (s.contains(required_value)) {  // Triplet is found; print the triplet  // elements  System.out.println('Triplet is ' + A[i]  + ', ' + A[j] + ', '  + required_value);  return true;  }  // Add the current element to the HashSet  // for future complement checks  s.add(A[j]);  }  }  // If no triplet is found, return false  return false;  }  public static void main(String[] args)  {  int[] A = { 1, 4, 45, 6, 10, 8 };  int sum = 22;  int arr_size = A.length;  // Call the find3Numbers function to find and print  // the triplet, if it exists  if (!find3Numbers(A, arr_size, sum)) {  System.out.println(  'No triplet found with the given sum.');  }  } }>

파이썬3

# Function to find a triplet with a given sum in an array> def> find3Numbers(arr,>sum>):> ># Fix the first element as arr[i]> >for> i>in> range>(>len>(arr)>-> 2>):> ># Create a set to store potential second elements that complement the desired sum> >s>=> set>()> ># Calculate the current sum needed to reach the target sum> >curr_sum>=> sum> -> arr[i]> ># Iterate through the subarray arr[i+1:]> >for> j>in> range>(i>+> 1>,>len>(arr)):> ># Calculate the required value for the second element> >required_value>=> curr_sum>-> arr[j]> ># Check if the required value is present in the set> >if> required_value>in> s:> ># Triplet is found; print the triplet elements> >print>(f>'Triplet is {arr[i]}, {arr[j]}, {required_value}'>)> >return> True> ># Add the current element to the set for future complement checks> >s.add(arr[j])> ># If no triplet is found, return False> >return> False> # Driver program to test above function> if> __name__>=>=> '__main__'>:> >arr>=> [>1>,>4>,>45>,>6>,>10>,>8>]> >target_sum>=> 22> ># Call the find3Numbers function to find and print the triplet, if it exists> >if> not> find3Numbers(arr, target_sum):> >print>(>'No triplet found.'>)>

씨#

using> System;> using> System.Collections.Generic;> class> Program {> >// Function to find a triplet with a given sum in an> >// array> >static> bool> Find3Numbers(>int>[] arr,>int> sum)> >{> >// Fix the first element as arr[i]> >for> (>int>

i = 0; i   // Create a HashSet to store potential second  // elements that complement the desired sum  HashSet s = 새로운 HashSet ();  // 목표 합계에 도달하는 데 필요한 // 현재 합계를 계산합니다. int curr_sum = sum - arr[i];  // 하위 배열 arr[i+1:]을 반복합니다. for (int j = i + 1; j // 두 번째 요소에 필요한 값을 계산합니다. // int require_value = curr_sum - arr[j]; // 필요한 값이 // HashSet에 있습니다. if (s.Contains(required_value)) { // 세 쌍이 발견되었습니다. // 요소를 인쇄합니다. Console.WriteLine('Triplet is ' + arr[i] + ', ' + arr[j] + ', ' + 필수_값); return true; } // 향후 보수 확인을 위해 // 현재 요소를 추가합니다. s.Add(arr[j]); 세 쌍이 발견되지 않으면 false를 반환합니다. return false; } // Find3Numbers 함수를 테스트하기 위한 드라이버 프로그램 static void Main() { int[] arr = { 1, 4, 45, 6, 10, 8 }; ; // Find3Numbers 함수를 호출하여 // 트리플렛이 있는 경우 이를 찾아 인쇄합니다. if (!Find3Numbers(arr, target_sum)) { Console.WriteLine('트리플렛을 찾을 수 없습니다.');

> 
    
   
      
  
     
      
     
    
 
     function> find3Numbers(A, sum) {> >// Fix the first element as A[i]> >for> (let i = 0; i   // Create a Set to store potential second elements that complement the desired sum  const s = new Set();  // Calculate the current sum needed to reach the target sum  const currSum = sum - A[i];  // Iterate through the subarray A[i+1..n-1] to find a pair with the required sum  for (let j = i + 1; j   // Calculate the required value for the second element  const requiredValue = currSum - A[j];  // Check if the required value is present in the Set  if (s.has(requiredValue)) {  // Triplet is found; print the triplet elements  console.log(`Triplet is ${A[i]}, ${A[j]}, ${requiredValue}`);  return true;  }  // Add the current element to the Set for future complement checks  s.add(A[j]);  }  }  // If no triplet is found, return false  return false; } function main() {  const A = [1, 4, 45, 6, 10, 8];  const sum = 22;  // Call the find3Numbers function to find and print the triplet, if it exists  if (!find3Numbers(A, sum)) {  console.log('No triplet found with the given sum.');  } } // Call the main function to start the program main();>  
 
 
 
    
 >
 
    
 >
 
  산출  
자바의 char + int
 Triplet is 4, 8, 10>
     시간 복잡도:    오(N^2)  
    보조 공간:    O(N), n개의 추가 공간을 차지했기 때문에
 문제에 대한 설명을 볼 수 있습니다.  유튜브  Geeks For Geeks 팀에서 논의했습니다.
 당신은 또한 참조할 수 있습니다  이것  유튜브에 올라온 영상.  
    주어진 합계로 모든 세 쌍을 인쇄하는 방법은 무엇입니까?       
나타내다 제로섬이 있는 모든 삼중항 찾기 .