K-Komplementære Par Med JavaScript

jeg har nylig hatt muligheten til å ta en kodeutfordring for et selskap som jeg virkelig beundrer, og vil gjerne jobbe med en dag. Jeg var takknemlig, spent og enda mer engstelig fordi det var mange ukjente som gikk inn i kodeutfordringen. Realiteten er at det er bare så mye du kan gjøre for å forberede:

• Bygg Prosjekter
• Studiealgoritmer
• Grind Problemer: LeetCode, HackerRank, CodeSignal

men den eneste måten å finne ut om du er klar, er å hoppe inn i den dype enden for å se om du kan flyte. Så jeg gjorde det, og jeg lærte så mye mer enn jeg noen gang hadde før, og på grunn av det ønsket jeg å dele det.

ved starten av oppgaven ble jeg møtt med tre oppgaver å fullføre. Jeg skal fokusere på bare 1 av disse i denne bloggen-K-Komplementære Par.

Målet

• du får Mål Heltall og En Matrise full av positive Heltall
• du må finne og finne komplementet Til Måltallet – noe som betyr at verdien av en indeks OG en annen indeks MÅ være Lik Målet
• Returner antall parene på slutten

numberArray + numberArray = 7

ovennevnte ville være et gyldig par siden disse to verdiene er lik målet.

Første Tilnærming

Da jeg først nærmet meg dette problemet, gikk jeg etter det på en brute force måte. Jeg trodde at jeg kunne bruke nestede løkker for å se etter de komplementære parene, og hei, jeg hadde rett! Det fungerte faktisk:

Hvordan fungerer Det?

• du løper over elementene i den første matrisen.
• du slår deretter over det sammen for å undersøke om Det er lik Målet gjennom hvert pass.
• hvis Målet er et treff, økes tellingen.

mens det virker, og jeg fikk en nøyaktig telling av de komplementære parene gitt et mål, var det ikke ideelt. Virkeligheten er at nestede løkker er sakte, og kan vokse eksponentielt gitt større arrays av elementer. Tidskompleksiteten For Den Er O (N2).

Andre Tilnærming-Optimalisering

så jeg gikk tilbake til tegnebrettet. Etter litt forskning og vurdering fant jeg ut at jeg kunne lagre verdiene i et objekt – {key: value}.

nå var dette fortsatt veldig vanskelig, spesielt siden jeg aldri har skrevet noe så komplekst før. Jeg gikk inn i nytt territorium, men jeg var spent fordi jeg faktisk kunne optimalisere min tidligere algoritme Til O (N):

Så hvordan fungerer det?

• Vet at numberArray Eller Lengden eksisterer.
• vi kjører gjennom numberArray først for å opprette nøkkel / verdipar i located_pairs-objektet. Gjennom denne prosessen vil det se etter unikhet og duplikater.
• vi løper over nøklene til det lokaliserte objektet og vet om det gjør det med målet. Hvis den gjør det, par teller økes.