K-perechi complementare cu JavaScript

recent am avut ocazia să fac o provocare de cod pentru o companie pe care o admir cu adevărat și aș dori să lucrez într-o zi. Am fost recunoscător, emoționat și cu atât mai nerăbdător, deoarece au existat o mulțime de necunoscute care au intrat în provocarea codului. Realitatea este că există doar atât de mult ai putea face pentru a pregăti:

• Construiți proiecte
• algoritmi de studiu
• Grind probleme: LeetCode, HackerRank,CodeSignal

cu toate acestea, singura modalitate de a afla dacă sunteți sau nu gata este să sari în capătul adânc pentru a vedea dacă ați putea pluti. Așa că am făcut-o, și am învățat mult mai mult decât am avut vreodată înainte, și din cauza asta am vrut să-l împărtășească.

la începutul misiunii am fost confruntat cu trei sarcini pentru a finaliza. Mă voi concentra doar pe 1 dintre acestea în acest blog-K-perechi complementare.

obiectivul

• vi se oferă întregul țintă și o matrice plină de numere întregi pozitive
• trebuie să găsiți și să localizați complementul la întregul țintă — ceea ce înseamnă că valoarea unui index și a unui alt indice trebuie să fie egală cu ținta
• returnați numărul de perechi la sfârșitul

numberArray + numberArray = 7

cele de mai sus ar fi o pereche validă, deoarece aceste două valori sunt egale cu ținta.

prima abordare

când am abordat prima dată această problemă, m-am dus după ea într-o manieră de forță brută. M-am gândit că aș putea folosi bucle imbricate pentru a verifica perechile complementare și hei, am avut dreptate! De fapt, a funcționat:

cum funcționează?

• vă buclați peste elementele matricei inițiale.
• apoi treceți peste el la unison pentru a verifica dacă este sau nu egal cu ținta prin fiecare trecere.
• dacă ținta este o potrivire, atunci numărul este incrementat.

în timp ce funcționează și am primit un număr precis al perechilor complementare date unei ținte, nu a fost ideal. Realitatea este că buclele imbricate sunt lente și pot crește exponențial, având în vedere matrice mai mari de elemente. Complexitatea timpului pentru aceasta este O (N2).

a doua abordare — optimizare

așa că m-am întors la placa de desen. După unele cercetări și considerații, am constatat că aș putea stoca valorile într — un obiect – {key: value}.

acum, acest lucru a fost încă foarte dificil, mai ales că nu am scris niciodată ceva atât de complex înainte. Am fost călcare în teritoriu nou, dar am fost încântat pentru că am fost de fapt capabil de a optimiza fostul meu algoritm la O (N):

deci, cum funcționează?

• Vet acel numărarray sau lungimea este existentă.
• rulăm mai întâi prin numberArray pentru a crea perechi cheie/valoare în obiectul located_pairs. De-a lungul acestui proces se va verifica pentru unicitatea și duplicate.
• apoi trecem peste tastele obiectului localizat și veterinarul pentru a afla dacă face sau nu cu ținta. Dacă o face, numărul de perechi este incrementat.