K-komplementære par med JavaScript

jeg havde for nylig muligheden for at tage en kodeudfordring for et firma, som jeg virkelig beundrer, og gerne vil arbejde med en dag. Jeg var taknemmelig, ophidset, og endnu mere så ængstelig, fordi der var mange ukendte, der gik ind i code challenge. Virkeligheden er, at der kun er så meget, du kan gøre for at forberede:

• bygge projekter
• undersøgelse algoritmer
• male problemer: LeetCode, HackerRank, CodeSignal

den eneste måde at finde ud af, om du er klar eller ej, er dog at hoppe ind i den dybe ende for at se, om du kunne flyde. Så det gjorde jeg, og jeg lærte så meget mere, end jeg nogensinde havde haft før, og på grund af det ville jeg dele det.

i starten af opgaven stod jeg over for tre opgaver, der skulle udføres. Jeg vil kun fokusere på 1 af disse i denne blog — k-komplementære par.

målet

• du får Målheltal og et Array fuld af positive heltal
• du skal finde og lokalisere komplementet til Målheltalet — hvilket betyder værdien af et indeks, og et andet indeks skal svare til målet
• returner antallet af parene i slutningen af det

numberArray + numberArray = 7

ovenstående ville være et gyldigt par, da disse to værdier svarer til målet.

første tilgang

da jeg først nærmede mig dette problem, gik jeg efter det på en brute force måde. Jeg troede, at jeg kunne bruge indlejrede sløjfer til at kontrollere de komplementære par, og hej, jeg havde ret! Det virkede faktisk:

Hvordan virker det?

• du løber over det oprindelige arrays elementer.
• du løber derefter over det unisont for at dyrlæge, om det er lig med målet gennem hver passage.
• hvis målet er et match, øges antallet.

mens det virker, og jeg modtog en nøjagtig optælling af de komplementære par givet et mål, var det ikke ideelt. Virkeligheden er, at indlejrede sløjfer er langsomme og kan vokse eksponentielt givet større arrays af elementer. Tidskompleksiteten for det er O (N2).

anden tilgang — optimering

så jeg gik tilbage til tegnebrættet. Efter nogle undersøgelser og overvejelser fandt jeg, at jeg kunne gemme værdierne i et objekt — {nøgle: værdi}.

nu var dette stadig meget vanskeligt, især da jeg aldrig har skrevet noget så komplekst før. Jeg trådte ind i nyt territorium, men jeg var begejstret, fordi jeg faktisk kunne optimere min tidligere algoritme til O (N):

så hvordan virker det?

• Vet det talarray eller længden findes.
• vi løber gennem nummeretarray først for at oprette nøgle/værdipar i objektet located_pairs. Gennem denne proces vil det kontrollere for entydighed og dubletter.
• vi kører derefter over nøglerne til det lokaliserede objekt og dyrlæge for, om det gør med målet eller ej. Hvis det gør det, øges antallet af par.