K-kompletterande par med JavaScript

jag hade nyligen möjlighet att ta en kod utmaning för ett företag som jag verkligen beundrar, och skulle vilja arbeta med en dag. Jag var tacksam, upphetsad, och ännu mer så orolig eftersom det fanns många okända som gick in i kodutmaningen. Verkligheten är att det bara finns så mycket du kan göra för att förbereda:

• bygg projekt
• Studiealgoritmer
• slipa problem: LeetCode, HackerRank, CodeSignal

det enda sättet att ta reda på om du är redo eller inte är att hoppa in i den djupa änden för att se om du kan flyta. Så jag gjorde, och jag lärde mig så mycket mer än jag någonsin haft tidigare, och på grund av det ville jag dela det.

i början av uppdraget stod jag inför tre uppgifter att slutföra. Jag kommer att fokusera på endast 1 av dessa i denna blogg — K-kompletterande par.

målet

• du får mål heltal och en Array full av positiva heltal
• du måste hitta och lokalisera komplement till målet heltal-vilket innebär att värdet av ett index och ett annat index måste vara lika med målet
• returnera räkningen av paren i slutet

numberArray + numberArray = 7

ovanstående skulle vara ett giltigt par eftersom dessa två värden är lika med målet.

första tillvägagångssättet

när jag först närmade mig denna fråga gick jag efter det på ett brute force sätt. Jag trodde att jag kunde använda kapslade slingor för att kontrollera om de kompletterande paren, och hej, jag hade rätt! Det fungerade faktiskt:

hur fungerar det?

• du loopar över den ursprungliga arrayens element.
• du slingrar sedan över det i samförstånd för att veta om det är lika med målet genom varje pass.
• om målet är en matchning ökas räkningen.

medan det fungerar, och jag fick ett exakt antal av de kompletterande paren som fick ett mål, var det inte idealiskt. Verkligheten är att kapslade slingor är långsamma och kan växa exponentiellt med större matriser av element. Tidskomplexiteten för den är O (N2).

andra metoden-optimering

så jag gick tillbaka till ritbordet. Efter lite forskning och övervägande fann jag att jag kunde lagra värdena i ett objekt — {key: value}.

nu var det fortfarande väldigt knepigt, särskilt eftersom jag aldrig har skrivit något så komplicerat tidigare. Jag trampade in i nytt territorium, men jag var upphetsad eftersom jag faktiskt kunde optimera min tidigare algoritm till O (N):

så hur fungerar det?

• Vet att numberArray eller längden finns.
• vi går igenom numberArray först för att skapa nyckel/värdepar i objektet located_pairs. Under hela denna process kommer det att kontrollera unikhet och dubbletter.
• vi kör sedan över nycklarna till det lokaliserade objektet och vet för huruvida det gör med målet eller inte. Om det gör det ökas antalet par.