K-Complementary Pairs with JavaScript

Recentemente ho avuto l’opportunità di accettare una sfida di codice per un’azienda che ammiro molto e con cui vorrei lavorare un giorno. Ero grato, eccitato e ancora più ansioso perché c’erano molte incognite nella sfida del codice. La realtà è che c’è solo così tanto che potresti fare per prepararti:

• Costruire progetti
• Algoritmi di studio
• Problemi Grind: LeetCode, HackerRank, CodeSignal

Tuttavia, l’unico modo per capire se sei pronto è saltare nella parte profonda per vedere se potresti galleggiare. Così ho fatto, e ho imparato molto di più di quanto avessi mai avuto prima, e per questo ho voluto condividerlo.

All’inizio del compito mi trovavo di fronte a tre compiti da completare. Mi concentrerò solo su 1 di questi in questo blog — K-Coppie complementari.

Obiettivo

• Si sono date Intero di Destinazione e una gamma completa di numeri Interi positivi
• Hai bisogno di trovare e individuare il complemento per l’Intero di Destinazione — il che significa che il valore di un indice e di un altro indice che DEVE essere uguale a Destinazione
• restituisce il conteggio delle coppie alla fine

numberArray + numberArray = 7

sarebbe una coppia valida dal momento che questi due valori uguali destinazione.

Primo approccio

Quando ho affrontato per la prima volta questo problema, l’ho seguito in modo bruto. Ho pensato di poter usare i loop nidificati per verificare le coppie complementari, e hey, avevo ragione! Ha funzionato davvero:

Come funziona?

• Si esegue il ciclo sugli elementi dell’array iniziale.
• Quindi lo si esegue all’unisono per verificare se è uguale o meno al Bersaglio attraverso ogni passaggio.
• Se l’obiettivo è una corrispondenza, il conteggio viene incrementato.

Mentre funziona, e ho ricevuto un conteggio accurato delle coppie complementari date a un target, non era l’ideale. La realtà è che i loop nidificati sono lenti e possono crescere esponenzialmente dati array di elementi più grandi. La complessità temporale è O (N2).

Secondo approccio — Ottimizzazione

Così sono tornato al tavolo da disegno. Dopo alcune ricerche e considerazioni, ho scoperto che potevo memorizzare i valori in un oggetto — {key: value}.

Ora, questo era ancora molto complicato, soprattutto perché non ho mai scritto qualcosa di così complesso prima. Stavo calpestando un nuovo territorio, ma ero eccitato perché ero in grado di ottimizzare il mio precedente algoritmo su O (N):

Quindi come funziona?

• Vet che numberArray o la Lunghezza esistente.
• Eseguiamo prima il numberArray per creare coppie chiave / valore nell’oggetto located_pairs. Durante questo processo controllerà l’unicità e i duplicati.
• Quindi eseguiamo le chiavi dell’oggetto localizzato e controlliamo se fa o meno con il bersaglio. Se lo fa, il conteggio delle coppie viene incrementato.