Gitt en matrise arr[] av størrelse n og et heltall X . Finn om det er en triplett i matrisen som summerer opp til det gitte heltall X .

Eksempler:

Inndata: matrise = {12, 3, 4, 1, 6, 9}, sum = 24;
Produksjon: 12, 3, 9
Forklaring: Det er en trilling (12, 3 og 9) til stede
i matrisen hvis sum er 24.

Inndata: matrise = {1, 2, 3, 4, 5}, sum = 9
Produksjon: 5, 3, 1
Forklaring: Det er en trilling (5, 3 og 1) til stede
i matrisen hvis sum er 9.

Triplettsum i matrise (3sum) ved å generere alle trillingene:

En enkel metode er å generere alle mulige tripletter og sammenligne summen av hver triplett med den gitte verdien. Følgende kode implementerer denne enkle metoden ved å bruke tre nestede løkker.

Steg-for-steg tilnærming:

• Gitt en rekke lengder n og en sum s
• Lag tre nestede løkke første løkkeløp fra start til slutt (løkketeller i), andre løkke går fra i+1 til slutt (løkketeller j) og tredje løkke går fra j+1 å avslutte (løkketeller k)
• Telleren til disse løkkene representerer indeksen til 3 elementer av trillingene.
• Finn summen av ith, jth og kth element. Hvis summen er lik gitt sum. Skriv ut tripletten og bryt.
• Hvis det ikke er noen triplett, skriv ut at ingen triplett eksisterer.

Nedenfor er implementeringen av tilnærmingen ovenfor:

C++

>

>

C

>

>

Java

>

>

Python3

hvordan kalle en metode i java

>

>

C#

>

>

Javascript

>

>

PHP

>

>

Triplet is 4, 10, 8>

Kompleksitetsanalyse:

• Tidskompleksitet: På³), Det er tre nestede løkker som krysser matrisen, så tidskompleksiteten er O(n^3)
• Hjelpeplass: O(1), Siden det ikke kreves ekstra plass.

Triplettsum i matrise (3sum) ved hjelp av To-peker teknikk :

Ved å sortere matrisen kan effektiviteten til algoritmen forbedres. Denne effektive tilnærmingen bruker to-pekers teknikk . Gå gjennom arrayet og fiks det første elementet i tripletten. Bruk nå Two Pointers-algoritmen for å finne om det er et par hvis sum er lik x – array[i] . To-pekeralgoritmen tar lineær tid, så den er bedre enn en nestet sløyfe.

Steg-for-steg tilnærming:

• Sorter den gitte matrisen.
• Sløyfe over arrayet og fiks det første elementet i den mulige tripletten, arr[i] .
• Deretter fikser du to pekere, en kl i + 1 og den andre kl n – 1 . Og se på summen,
  • Hvis summen er mindre enn den nødvendige summen, øker du den første pekeren.
  • Ellers, hvis summen er større, reduserer du sluttpekeren for å redusere summen.
  • Ellers, hvis summen av elementer ved to-pekeren er lik gitt sum, skriv ut tripletten og bryt.

Nedenfor er implementeringen av tilnærmingen ovenfor:

C++

>

>

C

>

>

Java

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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 # Hvis vi kommer hit, ble # ingen triplett funnet tilbake False # Driverprogram for å teste over funksjonen A = [1, 4, 45, 6, 10, 8] sum = 22 arr_size = len(A) find3Numbers(A, arr_size, sum) # Dette er bidratt av 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]>sum r--;  } } // Hvis vi når hit, så // ble ingen triplett funnet return false;  } int partisjon(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[] -->Array som skal sorteres si --> Startindeks ei --> Sluttindeks */ void quickSort(int[] A, int si, int ei) { int pi;  /* Partisjoneringsindeks */ if (si pi = partisjon(A, si, ei); quickSort(A, si, pi - 1); quickSort(A, pi + 1, ei); } } // Driverkode statisk tomrom Main() { GFG triplet = new GFG(); int[] A = new int[] { 1, 4, 45, 6, 10, 8 int arr_size = A.Length (A, arr_size, sum); } } // Denne koden er bidratt av mits>
 
 
 
 
    
 
>
 
    
 
>
 
 
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;> >/* 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]>sum r--;  } } // Hvis vi når hit, ble ingen triplett funnet return false; } /* Driverprogram for å teste funksjonen ovenfor */ la A = [ 1, 4, 45, 6, 10, 8 ];  la sum = 22;  la arr_size = A.length;  find3Numbers(A, arr_size, sum); // Denne koden er bidratt av 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]>sum $r--;  } } // Hvis vi når hit, så // ble ingen triplett funnet return false; } // Driverkode $A = array (1, 4, 45, 6, 10, 8); $sum = 22; $arr_size = sizeof($A); find3Numbers($A, $arr_size, $sum); // Denne koden er bidratt av ajit ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Produksjon  
 
Triplet is 4, 8, 10>
 
    Kompleksitetsanalyse:     
 
 
    Tidskompleksitet:    O(N^2), Det er bare to nestede løkker som krysser matrisen, så tidskompleksiteten er O(n^2). To-pekeralgoritmen tar O(n) tid og det første elementet kan fikses ved hjelp av en annen nestet traversering.
 
    Hjelpeplass:    O(1), Siden det ikke kreves ekstra plass.
 
 
    Triplettsum i matrise (3sum)    ved hjelp av  Hashing  :
  
 
Denne tilnærmingen bruker ekstra plass, men er enklere enn to-peker-tilnærmingen. Kjør to løkker ytre løkke fra start til slutt og indre løkke fra    i+1    å ende. Lag et hashmap eller sett for å lagre elementene i mellom    i+1    til    n-1    . Så hvis den gitte summen er    x,    sjekk om det er et tall i settet som er lik    x         – arr[i] – arr[j]    . Hvis ja, skriv ut tripletten.
 
 
Steg-for-steg tilnærming:
 
 
Iterer gjennom matrisen, fikser det første elementet (    A[i]    ) for trillingen.
 
For hver    A[i]    , bruk en Hashmap         å lagre potensielle andre elementer som fullfører den ønskede summen    (sum – A[i])    .
 
Inne i en nestet sløyfe, sjekk om forskjellen mellom det gjeldende elementet (    A[j]    ) og ønsket sum (    sum – A[i]    ) finnes i Hashmap. Hvis det er det, blir en triplett funnet, så skriv den ut.
 
Hvis ingen triplett er funnet i hele matrisen, returnerer funksjonen    falsk    .
 
 
Nedenfor er implementeringen av tilnærmingen ovenfor:
 
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;  // Beregn gjeldende sum som trengs for å nå // målsum int curr_sum = sum - A[i];  // Iterer gjennom undermatrisen A[i+1..n-1] for å finne // et par med den nødvendige summen for (int j = i + 1; j // Beregn den nødvendige verdien for det andre // elementet int required_value = curr_sum - A[j]; // Sjekk om den nødvendige verdien er tilstede i //-settet hvis (s.find(required_value) != s.end()) { // Skriv ut tripletten /; / elementer printf('Trippel er %d, %d, %d', A[i], A[j], returnert sann } // Legg til det gjeldende elementet for fremtidig // komplement sjekker s.insert(A[j]); 4, 45, 6, 10, 8 }; int sum = 22; int arr_size = sizeof(A) / sizeof(A[0]); 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 = nytt HashSet ();  // Beregn gjeldende sum som trengs for å nå // målsum int curr_sum = sum - arr[i];  // Iterer gjennom undermatrisen arr[i+1:] for (int j = i + 1; j // Beregn den nødvendige verdien for // andre elementet int required_value = curr_sum - arr[j]; // Sjekk om nødvendig verdi er tilstede i // HashSet if (s.Contains(required_value)) { // Triplett er funnet skriv ut tripletten // elementene Console.WriteLine('Triplett er ' + arr[i] + ', ' + arr[j] + ', ' + required_value return true } // Legg til det gjeldende elementet til HashSet // for fremtidige komplementkontroller s.Add(arr[j]); Hvis ingen triplett blir funnet, returner false return false } // Driverprogram for å teste Find3Numbers-funksjonen static void Main() { int[] arr = { 1, 4, 45, 6, 10, 8 }; ; // Kall Find3Numbers-funksjonen for å finne og skrive ut // tripletten, hvis den finnes hvis (!Find3Numbers(arr, target_sum)) { Console.WriteLine('Ingen triplett funnet.');
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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();>
 
 
 
 
    
 
>
 
    
 
>
 
  Produksjon  
fang og prøv java
 
Triplet is 4, 8, 10>
 
    Tidskompleksitet:    O(N^2)  
    Hjelpeplass:    O(N), siden n ekstra plass er tatt
 
Du kan se forklaringen av problemet på  YouTube  diskutert av Geeks For Geeks Team.
 
Du kan også henvise  dette  video til stede på Youtube.  
    Hvordan skrive ut alle trillinger med gitt sum?       
Henvise Finn alle trillinger med nullsum .