Dato un array arr[] di dimensione N e un numero intero X . Scopri se c'è una tripletta nell'array che somma il numero intero indicato X .

Esempi:

Ingresso: matrice = {12, 3, 4, 1, 6, 9}, somma = 24;
Produzione: 12, 3, 9
Spiegazione: È presente una terzina (12, 3 e 9).
nell'array la cui somma è 24.

Ingresso: matrice = {1, 2, 3, 4, 5}, somma = 9
Produzione: 5, 3, 1
Spiegazione: È presente una terzina (5, 3 e 1).
nell'array la cui somma è 9.

Somma tripletta nell'array (somma 3) generando tutte le triplette:

Un metodo semplice è generare tutte le triplette possibili e confrontare la somma di ciascuna tripletta con il valore dato. Il codice seguente implementa questo semplice metodo utilizzando tre cicli nidificati.

Approccio passo dopo passo:

• Dato un array di lunghezza N e una somma S
• Crea tre cicli nidificati: il primo ciclo viene eseguito dall'inizio alla fine (contatore del ciclo i), il secondo ciclo viene eseguito da io+1 alla fine (contatore del ciclo j) e il terzo ciclo parte da j+1 per terminare (contatore del ciclo k)
• Il contatore di questi cicli rappresenta l'indice di 3 elementi delle terzine.
• Trova la somma di iesimo, jesimo e kesimo elemento. Se la somma è uguale alla somma data. Stampa la terzina e spezzala.
• Se non c'è una terzina, stampa che non esiste una terzina.

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

C++

>

>

C

>

>

Giava

>

>

Python3

>

>

C#

>

>

Javascript

>

>

PHP

>

>

Triplet is 4, 10, 8>

Analisi della complessità:

• Complessità temporale: SU³), Ci sono tre cicli nidificati che attraversano l'array, quindi la complessità temporale è O(n^3)
• Spazio ausiliario: O(1), poiché non è richiesto spazio aggiuntivo.

Somma tripletta nell'array (somma 3) utilizzando Tecnica dei due puntatori :

Ordinando l'array è possibile migliorare l'efficienza dell'algoritmo. Questo approccio efficiente utilizza il file tecnica dei due puntatori . Attraversa l'array e fissa il primo elemento della tripletta. Ora usa l'algoritmo Two Pointers per scoprire se esiste una coppia la cui somma è uguale a x – matrice[i] . L'algoritmo a due puntatori richiede tempo lineare, quindi è migliore di un ciclo annidato.

Approccio passo dopo passo:

• Ordina l'array indicato.
• Passa sull'array e fissa il primo elemento della possibile tripletta, arr[i] .
• Quindi fissa due puntatori, uno a io + 1 e l'altro a n-1 . E guarda la somma,
  • Se la somma è inferiore alla somma richiesta, incrementare il primo puntatore.
  • Altrimenti, se la somma è maggiore, diminuire il puntatore finale per ridurre la somma.
  • Altrimenti, se la somma degli elementi su due puntatori è uguale alla somma data, stampa la terzina e spezza.

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

C++

sciacallo contro lupo

>

>

C

>

>

Giava

>

>

Python3

>

>

C#

>

>

Javascript

>

>

PHP

join e tipi di join

>

>

Triplet is 4, 8, 10>

Analisi della complessità:

• Complessità temporale: O(N^2), ci sono solo due cicli nidificati che attraversano l'array, quindi la complessità temporale è O(n^2). L'algoritmo a due puntatori richiede tempo O(n) e il primo elemento può essere corretto utilizzando un altro attraversamento nidificato.
• Spazio ausiliario: O(1), poiché non è richiesto spazio aggiuntivo.

Somma tripletta nell'array (somma 3) utilizzando Hashing :

Questo approccio utilizza spazio aggiuntivo ma è più semplice dell'approccio a due puntatori. Esegui due cicli del ciclo esterno dall'inizio alla fine e del ciclo interno da io+1 finire. Crea una mappa hash o un set per memorizzare gli elementi intermedi io+1 A n-1 . Quindi, se la somma data è X, controlla se c'è un numero nel set che è uguale a X – arr[i] – arr[j] . Se sì, stampa la terzina.

Approccio passo dopo passo:

• Scorrere l'array, fissando il primo elemento ( A[i] ) per la terzina.
• Per ciascuno A[i] , usa una Hashmap per memorizzare potenziali secondi elementi che completano la somma desiderata (somma – A[i]) .
• All'interno di un ciclo annidato, controlla se la differenza tra l'elemento corrente ( A[j] ) e la somma desiderata ( somma – A[i] ) è presente nell'Hashmap. Se lo è, viene trovata una tripletta, quindi stampala.
• Se non viene trovata alcuna tripletta nell'intero array, la funzione restituisce falso .

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

C++

>

>

Giava

>

>

Python3

>

>

C#

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 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();>
 
 
 
 
    
 
>
 
    
 
>
 
  Produzione  
 
Triplet is 4, 8, 10>
 
    Complessità temporale:    O(N^2)  
    Spazio ausiliario:    O(N), poiché è stato occupato n spazio aggiuntivo
 
Puoi guardare la spiegazione del problema su  Youtube  discusso dal team Geeks For Geeks.
 
Puoi anche fare riferimento  Questo  video presente su Youtube.  
    Come stampare tutte le terzine con una determinata somma?       
Fare riferimento Trova tutte le triplette con somma zero .