配列が与えられた場合 到着[] サイズの 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) すべてのトリプレットを生成することで、次のようになります。

簡単な方法は、考えられるすべてのトリプレットを生成し、すべてのトリプレットの合計を指定された値と比較することです。次のコードは、3 つのネストされたループを使用してこの単純なメソッドを実装します。

段階的なアプローチ:

• 長さの配列が与えられた場合 n そして合計 s
• 3 つのネストされたループを作成します。最初のループは最初から最後まで実行され (ループ カウンター i)、2 番目のループは次から実行されます。 i+1 から終了 (ループ カウンタ j) まで、そして 3 番目のループは次から実行されます。 j+1 終了まで(ループカウンタk)
• これらのループのカウンターは、次のインデックスを表します。 3 トリプレットの要素。
• i 番目、j 番目、k 番目の要素の合計を求めます。合計が指定された合計と等しい場合。 3 連符を出力して改行します。
• トリプレットが存在しない場合は、トリプレットが存在しないことを出力します。

上記のアプローチの実装を以下に示します。

C++

>

>

C

>

>

ジャワ

>

ラドヤード・キプリングによる要約の場合

>

Python3

>

>

C#

>

>

JavaScript

>

>

PHP

>

>

Triplet is 4, 10, 8>

複雑さの分析:

• 時間計算量: の上³)、配列を横断する 3 つのネストされたループがあるため、時間計算量は O(n^3) になります。
• 補助スペース: O(1)、余分なスペースは必要ありません。

配列内のトリプレットの合計 (3sum) を使用して ツーポインターテクニック :

配列をソートすることにより、アルゴリズムの効率を向上させることができます。この効率的なアプローチでは、 ツーポインターテクニック 。配列を走査し、トリプレットの最初の要素を修正します。次に、Two Pointers アルゴリズムを使用して、合計が次と等しいペアがあるかどうかを調べます。 x – 配列[i] 。 2 ポインター アルゴリズムは線形時間がかかるため、ネストされたループよりも優れています。

段階的なアプローチ:

• 指定された配列をソートします。
• 配列をループし、可能なトリプレットの最初の要素を修正します。 到着しました 。
• 次に、2 つのポインターを修正します。1 つは次の位置です。 私+1 そしてもう一つは n – 1 。そして合計を見てみると、
  • 合計が必要な合計より小さい場合は、最初のポインタをインクリメントします。
  • それ以外の場合、合計が大きい場合は、終了ポインタを減らして合計を減らします。
  • それ以外の場合、2 ポインターの要素の合計が指定された合計と等しい場合は、3 つ組を出力して中断します。

上記のアプローチの実装を以下に示します。

C++

>

>

C

>

>

ジャワ

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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# 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 パーティション(int[] A, int si, int ei) { int x = A[ei];  int i = (si - 1);  int j;  for (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>>' によって提供されました。
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > // 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;> >/* Sort the elements */> >A.sort((a,b) =>a-b);>> /* Now fix the first element one> >by one and find the> >other two elements */> >for> (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); $sum = 22; $arr_size = sizeof($A); find3Numbers($A, $arr_size, $sum); // このコードは ajit によって提供されました ?>>>
 
 
 
 
    
 
>
 
    
 
>
 
  出力  
 
Triplet is 4, 8, 10>
 
    複雑さの分析:     
 
 
    時間計算量:    O(N^2)、配列を横断するネストされたループは 2 つだけであるため、時間計算量は O(n^2) です。 2 ポインター アルゴリズムには O(n) 時間がかかり、最初の要素は別のネストされたトラバーサルを使用して修正できます。
 
    補助スペース:    O(1)、余分なスペースは必要ありません。
 
 
    配列内のトリプレットの合計 (3sum)    を使用して  ハッシュ化  :
  
 
このアプローチでは余分なスペースが使用されますが、2 ポインターのアプローチよりも単純です。 2 つのループを外側のループを最初から最後まで実行し、内側のループを最初から最後まで実行します。    i+1    最後まで。ハッシュマップを作成するか、その間の要素を保存するように設定します    i+1    に    n-1    。したがって、与えられた合計が    バツ、    セット内に以下に等しい数値があるかどうかを確認します    バツ         – arr[i] – arr[j]    。 「はい」の場合、トリプレットを出力します。
 
 
段階的なアプローチ:
 
 
配列を反復処理して、最初の要素を固定します (    A[i]    ) トリプレットの場合。
 
それぞれについて    A[i]    、ハッシュマップを使用する         必要な合計を完成させる潜在的な 2 番目の要素を格納する    (合計 – 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 s;  // 目標合計に達するために必要な現在の合計を計算します // int curr_sum = sum - A[i];  // 部分配列 A[i+1..n-1] を反復処理して、 // 必要な和を持つペアを見つけます (int j = i + 1; j // 2 番目の要素に必要な値を計算します // 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); // 将来の補完のために現在の要素をセットに追加します。 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 関数を呼び出して出力します。 find3Numbers(A, arr_size, sum); }>>'
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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 = 新しいハッシュセット ();  // 目標合計に達するために必要な現在の合計を計算します // int curr_sum = sum - arr[i];  // 部分配列 arr[i+1:] を繰り返し処理します for (int j = i + 1; j // 2 番目の要素に必要な値を計算します // int required_value = curr_sum - arr[j]; // かどうかを確認します// 必要な値が HashSet に存在します if (s.Contains(required_value)) { // トリプレットが見つかりました; // 要素を表示します Console.WriteLine('Triplet is ' + arr[i] + ', ' + arr[j] + ', ' + required_value); } // 将来の補数チェックのために、現在の要素を HashSet に追加します。 } } //トリプレットが見つからない場合は 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();>
 
 
 
 
    
 
>
 
    
 
>
 
  出力  
 
Triplet is 4, 8, 10>
 
    時間計算量:    O(N^2)  
    補助スペース:    O(N)、n 個の余分なスペースが取られているため
 
問題の説明は次のサイトで見ることができます  YouTube  Geeks For Geeks チームによって議論されました。
 
参照することもできます  これ  Youtubeで動画プレゼント中。  
    指定された合計を持つすべての 3 つ組を出力するにはどうすればよいですか?       
参照する ゼロ和を持つすべての三重項を検索します 。