K-complementary Pairs with JavaScript

nemrég volt alkalmam, hogy egy kód kihívás egy cég, hogy igazán csodálom, és szeretnék dolgozni egy nap. Hálás voltam, izgatott, és még inkább ideges, mert sok ismeretlen volt a kód kihívás. A valóság az, hogy csak annyit tehet, hogy felkészüljön:

• Építsd projektek
• tanulmány algoritmusok
• Grind problémák: LeetCode, HackerRank, CodeSignal

azonban az egyetlen módja annak, hogy kitaláljuk, hogy készen állsz-e vagy sem, hogy ugorj a mélyvízbe, hogy megnézhesd, tudsz-e lebegni. Így is tettem, és sokkal többet tanultam, mint valaha, és ezért szerettem volna megosztani.

a feladat kezdetén három feladatot kellett elvégeznem. Csak erre fogok összpontosítani 1 ezek közül ebben a blogban-K-kiegészítő Párok.

a cél

• Ön adott cél egész és egy tömb tele pozitív egészek
• meg kell találni, és keresse meg a komplement a cél egész — ami azt jelenti, az érték egy index és egy másik index meg kell egyeznie a cél
• visszaadja a száma a párok végén

számarray + számarray = 7

a fentiek érvényes pár lennének, mivel ez a két érték megegyezik a céllal.

első megközelítés

amikor először közelítettem meg ezt a kérdést, brute force módon mentem utána. Azt hittem, hogy a beágyazott hurkok segítségével ellenőrizhetem a kiegészítő párokat, és hé, igazam volt! Valójában működött:

hogyan működik?

• hurkolja át a kezdeti tömb elemeit.
• ezután hurok rajta kórusban állatorvos-e vagy sem egyenlő a cél keresztül minden menetben.
• ha a cél egyezés, akkor a szám növekszik.

bár működik, és pontos számot kaptam a célhoz adott kiegészítő párokról, nem volt ideális. A valóság az, hogy a beágyazott hurkok lassúak, és exponenciálisan növekedhetnek, ha nagyobb elemtömböket kapnak. Az idő bonyolultsága O (N2).

második megközelítés — optimalizálás

tehát visszamentem a rajztáblához. Némi kutatás és megfontolás után rájöttem, hogy az értékeket egy objektumban tárolhatom — {key: value}.

ez még mindig nagyon trükkös volt, különösen azért, mert még soha nem írtam ilyen bonyolult dolgot. Új területre léptem, de izgatott voltam, mert valójában képes voltam optimalizálni a korábbi algoritmusomat O(N):

tehát hogyan működik?

• Vet, hogy numberArray vagy a hossza létezik.
• először a numberarray-n futunk át, hogy kulcs/érték párokat hozzunk létre a located_pairs objektumban. A folyamat során ellenőrizni fogja az egyediséget és a másolatokat.
• ezután átfutjuk a lokalizált objektum kulcsait, és megvizsgáljuk, hogy a célponttal működik-e vagy sem. Ha igen, a párok száma növekszik.