ТРИПЛЕТНА СУМА В МАСИВІ (3СУМИ) - TECHCODEVIEW.COM

Дано масив обр[] розміру п і ціле число X . Знайдіть, чи є в масиві трійка, яка дорівнює вказаному цілому числу X .

приклади:

введення: масив = {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.

Рекомендована практика Потрійна сума в масиві Спробуйте!

Триплетна сума в масиві (3суми) генеруючи всі трійки:

Простий метод полягає у створенні всіх можливих триплетів і порівнянні суми кожного триплету з заданим значенням. Наступний код реалізує цей простий метод за допомогою трьох вкладених циклів.

Покроковий підхід:

Дано масив довжини п і суму с
Створіть три вкладені цикли, перший цикл виконується від початку до кінця (лічильник циклу i), другий цикл запускається з i+1 до кінця (лічильник циклу j) і починається третій цикл j+1 до кінця (лічильник циклу k)
Лічильник цих циклів представляє індекс 3 елементи трійки.
Знайдіть суму 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>

C

#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

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

Python3

# 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#

// 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

> // 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³), є три вкладені цикли, що перетинають масив, тому часова складність становить O(n^3)
Допоміжний простір: O(1), оскільки додатковий простір не потрібен.

Триплетна сума в масиві (3суми) використовуючи Техніка двох указок :

Завдяки сортуванню масиву можна підвищити ефективність алгоритму. Цей ефективний підхід використовує техніка двох очків . Перейдіть по масиву та зафіксуйте перший елемент трійки. Тепер скористайтеся алгоритмом двох покажчиків, щоб знайти пару, сума якої дорівнює x – масив[i] . Алгоритм із двома вказівниками займає лінійний час, тому він кращий, ніж вкладений цикл.

Покроковий підхід:

Відсортуйте заданий масив.
Перейдіть по масиву та зафіксуйте перший елемент можливого триплету, arr[i] .
Потім зафіксуйте два покажчики, один на я + 1 а інший при n – 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 };  int sum = 22;  int arr_size = sizeof(A) / sizeof(A[0]);  find3Numbers(A, arr_size, sum);  повернути 0; } // Цей код створено Aditya Kumar (adityakumar129)>

C

// 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 };  int sum = 22;  int arr_size = sizeof(A) / sizeof(A[0]);  find3Numbers(A, arr_size, sum);  повернути 0; } // Цей код створено Aditya Kumar (adityakumar129)>

Java

// 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 main(String[] args) { FindTriplet = new FindTriplet(); int arr_size = A. length; triplet.find3Numbers(A, arr_size, sum); }>

Python3

# 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>

найкраща усмішка в світі

C#

// 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); } } // Статичний недійсний код драйвера Main() { GFG triplet (); int[] A = new int[] { 1, 4, 6, 10, 8 }; int arr_size = A.Length.find3Numbers (A, arr_size, sum); // Цей код створено mits>

Javascript

(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), оскільки додатковий простір не потрібен.

Триплетна сума в масиві (3суми) використовуючи Хешування :

Цей підхід використовує додатковий простір, але є простішим, ніж підхід двох вказівників. Виконайте два цикли зовнішній цикл від початку до кінця та внутрішній цикл від i+1 до кінця. Створіть хеш-карту або набір для зберігання елементів між ними i+1 до n-1 . Отже, якщо задана сума х, перевірте, чи є в наборі число, яке дорівнює x – arr[i] – arr[j] . Якщо так, виведіть триплет.

Покроковий підхід:

Перебираємо масив, фіксуючи перший елемент ( A[i] ) для трійки.
Для кожного A[i] , використовуйте Hashmap для зберігання потенційних других елементів, які доповнюють бажану суму (сума – A[i]) .
Усередині вкладеного циклу перевірте, чи різниця між поточним елементом ( A[j] ) і шукану суму ( сума – A[i] ) присутній у Hashmap. Якщо так, знайдено триплет, виведіть його.
Якщо триплет не знайдено у всьому масиві, функція повертає помилковий .

Нижче наведено реалізацію вищезазначеного підходу:

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 s;  // Обчислити поточну суму, необхідну для досягнення // цільової суми int curr_sum = sum - A[i];  // Перебираємо підмасив A[i+1..n-1], щоб знайти // пару з необхідною сумою для (int j = i + 1; j // Обчислюємо необхідне значення для другого // елемента int required_value = curr_sum - A[j]; // Перевірте, чи присутнє потрібне значення // у наборі if (s.find(required_value) != s.end()) { // Триплет знайдено; / elements printf('Triplet is %d, %d, %d', A[i], A[j], return true; } // Додати поточний елемент до набору для майбутнього доповнення перевіряє s.insert(A[j]); // Якщо триплет не знайдено, повертає false return false } /* Програма драйвера для перевірки функції */ int main() { int A[] = { 1, 4, 45, 6, 10, 8 }; int arr_size = sizeof(A[0]); // Виклик функції find3Numbers, якщо вона існує find3Numbers(A, arr_size, sum); return 0;>

Java

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

Python3

# 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.'>)>

C#

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 required_value = curr_sum - arr[j]; // Перевірка, чи потрібне значення присутнє в // HashSet if (s.Contains(required_value)) { // Триплет знайдено; // елементи Console.WriteLine('Triplet is ' + arr[i] + ', ' + arr[j] + ' + required_value } // Додати поточний елемент до HashSet // для майбутніх перевірок доповнення s.Add(arr[j]); Якщо триплет не знайдено, повертає false; } // Програма драйвера для перевірки функції Find3Numbers static void Main() { int[] arr = { 1, 4, 45, 6, 10, 8 }; int target_sum = 22 ; // Виклик функції Find3Numbers, щоб знайти та надрукувати // триплет, якщо він існує if (!Find3Numbers(arr, target_sum)) { Console.WriteLine('Тріплет не знайдено.'); } } }>

Javascript

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

Вихід

Triplet is 4, 8, 10>

Часова складність: O(N^2)
Допоміжний простір: O(N), оскільки n додаткового місця було зайнято

Ви можете переглянути пояснення задачі на YouTube обговорюється командою Geeks For Geeks.

Ви також можете звернутися це відео представлено на Youtube.
Як надрукувати всі трійки із заданою сумою?
Зверніться Знайти всі трійки з нульовою сумою .