K-complementaire paren met JavaScript

ik had onlangs de kans om een code uitdaging aan te gaan voor een bedrijf dat ik echt bewonder, en zou graag willen werken met een dag. Ik was dankbaar, opgewonden, en nog meer zo angstig omdat er veel onbekenden gaan in de code uitdaging. De realiteit is dat je maar zoveel kunt doen om je voor te bereiden.:

• bouwprojecten
• Studiealgoritmen
• problemen oplossen: LeetCode, HackerRank, CodeSignal

echter, de enige manier om erachter te komen of je klaar bent is om in het diepe te springen om te zien of je zou kunnen zweven. Dus dat deed ik, en ik leerde zoveel meer dan ooit tevoren, en daarom wilde ik het delen.

aan het begin van de opdracht moest ik drie taken uitvoeren. Ik zal me richten op slechts 1 van deze in deze blog-K-complementaire paren.

Doel

• U bepaalde Doelstelling een Integer en een Matrix vol van positieve gehele Getallen
• Je nodig hebt te vinden en zoek de aanvulling van het Doel Integer — wat betekent dat de waarde van een index en een andere index MOET gelijk zijn aan de Target
• de Terugkeer van de telling van de paren aan het einde

numberArray + numberArray = 7

Het zou een geldig paar aangezien deze twee waarden gelijk zijn aan de doelgroep.

eerste benadering

toen ik deze kwestie voor het eerst benaderde, ging ik er met brute kracht achteraan. Ik dacht dat ik geneste lussen kon gebruiken om te controleren op de complementaire paren, en hey, ik had gelijk! Het werkte echt:

Hoe werkt het?

• je lus over de elementen van de initiële array.
• u lus er dan in koor over om te controleren of het al dan niet gelijk is aan het doel door elke pass.
• als het doel overeenkomt, wordt het aantal verhoogd.

hoewel het werkt, en ik kreeg een nauwkeurige telling van de complementaire paren gegeven een doel, het was niet ideaal. De realiteit is dat geneste lussen zijn traag, en exponentieel kan groeien gegeven Grotere arrays van elementen. De tijdscomplexiteit hiervoor is O (N2).

tweede benadering-optimalisatie

dus ging ik terug naar de tekentafel. Na wat onderzoek en overweging, vond ik dat ik de waarden kon opslaan in een object — {key: value}.

dit was nog steeds erg lastig, vooral omdat ik nog nooit zoiets complexs heb geschreven. Ik was het betreden van nieuw terrein, maar ik was opgewonden omdat ik was eigenlijk in staat om mijn voormalige algoritme te optimaliseren om O (N):

dus hoe werkt het?

• Controleer of het getal of de lengte bestaat.
• we lopen eerst door de numberArray om sleutel/waarde paren aan te maken in het located_pairs object. Gedurende dit proces zal het controleren op uniciteit en duplicaten.
• we lopen dan over de sleutels van het gelocaliseerde object en controleren of het al dan niet maakt met het doel. Als dat zo is, wordt het aantal paren verhoogd.