k-komplementární páry s JavaScriptem

nedávno jsem měl příležitost přijmout výzvu kódu pro společnost, kterou opravdu obdivuji, a rád bych s ní pracoval jeden den. Byl jsem vděčný, nadšený, a ještě více tak nervózní, protože do výzvy code challenge šlo spousta neznámých. Realita je taková, že je tu jen tolik, co můžete udělat pro přípravu:

• stavět projekty
• studijní algoritmy
• Grind problémy: LeetCode, HackerRank, CodeSignal

jediným způsobem, jak zjistit, zda jste připraveni, je skočit do hlubokého konce, abyste zjistili, zda byste mohli plavat. Tak jsem to udělal, a naučil jsem se mnohem víc, než jsem kdy předtím, a proto jsem se o to chtěl podělit.

na začátku úkolu jsem byl konfrontován se třemi úkoly. Zaměřím se pouze na 1 z nich v tomto blogu-k-komplementární páry.

Cílem

• Ty jsou uvedeny Cílové Číslo, a Pole plná pozitivní Celá čísla
• musíte najít a vyhledejte doplněk k Cílové Číslo, což znamená, že hodnota jedné index a nový index MUSÍ rovnat Cíl
• Návrat počet párů na konci

numberArray + numberArray = 7

výše uvedené by být platný pár, protože se tyto dvě hodnoty rovnají cíl.

první přístup

když jsem se poprvé přiblížil k tomuto problému, šel jsem po něm hrubou silou. Myslel jsem, že bych mohl použít vnořené smyčky ke kontrole doplňkových párů, a hej, měl jsem pravdu! To skutečně fungovalo:

Jak to funguje?

• smyčkujete prvky počátečního pole.
• pak smyčku přes něj v souzvuku prověřit, zda se rovná cíl prostřednictvím každého průchodu.
• pokud je cílem shoda, počet se zvýší.

i když to funguje, a dostal jsem přesný počet komplementárních párů vzhledem k cíli, nebylo to ideální. Skutečnost je taková, že vnořené smyčky jsou pomalé a mohou exponenciálně růst vzhledem k větším polím prvků. Časová složitost je O (N2).

druhý přístup-optimalizace

tak jsem se vrátil k rýsovacímu prknu. Po nějakém výzkumu a zvážení jsem zjistil, že mohu hodnoty uložit do objektu — {key: value}.

nyní to bylo stále velmi složité, zejména proto, že jsem nikdy nenapsal něco tak složitého. Byl jsem šlapal do nových území, ale byl jsem nadšený, protože jsem byl vlastně schopen optimalizovat můj bývalý algoritmus O(N):

Takže jak to funguje?

• veterinář toto číslo nebo Délka existuje.
• nejprve projdeme numberArray a vytvoříme páry klíčů/hodnot v objektu located_pairs. Během tohoto procesu bude kontrolovat jedinečnost a duplikáty.
• pak přejdeme přes klíče umístěného objektu a prověříme, zda to dělá s cílem. Pokud ano, počet párů se zvýší.