K-Complementary Pairs with JavaScript
Ich hatte kürzlich die Gelegenheit, eine Code-Herausforderung für ein Unternehmen anzunehmen, das ich wirklich bewundere und mit dem ich eines Tages zusammenarbeiten möchte. Ich war dankbar, aufgeregt und noch ängstlicher, weil es viele Unbekannte gab, die an der Code-Herausforderung teilnahmen. Die Realität ist, dass Sie nur so viel tun können, um sich vorzubereiten:
- Projekte erstellen
- Algorithmen studieren
- Probleme lösen: LeetCode, HackerRank, CodeSignal
Die einzige Möglichkeit, herauszufinden, ob Sie bereit sind oder nicht, besteht darin, ins tiefe Ende zu springen, um zu sehen, ob Sie schweben können. Also habe ich es getan, und ich habe so viel mehr gelernt als je zuvor, und deshalb wollte ich es teilen.
Zu Beginn des Auftrags hatte ich drei Aufgaben zu erledigen. Ich werde mich in diesem Blog nur auf 1 konzentrieren – K-komplementäre Paare.
Das Ziel
- Sie erhalten eine Ziel-Ganzzahl und ein Array voller positiver Ganzzahlen
- Sie müssen das Komplement zur Ziel—Ganzzahl finden und lokalisieren – was bedeutet, dass der Wert eines Index und eines anderen Index dem Ziel entsprechen muss
- Geben Sie die Anzahl der Paare am Ende
numberArray + numberArray = 7
Das obige wäre ein gültiges Paar, da diese beiden Werte dem Ziel entsprechen.
Erster Ansatz
Als ich mich diesem Problem zum ersten Mal näherte, ging ich ihm auf rohe Gewalt nach. Ich dachte, ich könnte verschachtelte Schleifen verwenden, um nach den komplementären Paaren zu suchen, und hey, ich hatte Recht! Es hat tatsächlich funktioniert:
Wie funktioniert es?
- Sie durchlaufen die Elemente des anfänglichen Arrays.
- Sie durchlaufen es dann gemeinsam, um zu überprüfen, ob es in jedem Durchgang dem Ziel entspricht oder nicht.
- Wenn das Ziel eine Übereinstimmung ist, wird die Anzahl erhöht.
Während es funktioniert und ich eine genaue Anzahl der komplementären Paare erhalten habe, war es nicht ideal. Die Realität ist, dass verschachtelte Schleifen langsam sind und bei größeren Arrays von Elementen exponentiell wachsen können. Die Zeitkomplexität dafür ist O (N2).
Zweiter Ansatz – Optimierung
Also ging ich zurück zum Zeichenbrett. Nach einigen Recherchen und Überlegungen stellte ich fest, dass ich die Werte in einem Objekt speichern konnte — {key: value} .
Nun, das war immer noch sehr schwierig, zumal ich noch nie etwas so Komplexes geschrieben habe. Ich betrat Neuland, war aber aufgeregt, weil ich meinen früheren Algorithmus tatsächlich auf O (N) optimieren konnte):
Wie funktioniert es?
- Gibt an, dass numberArray oder die Länge vorhanden ist.
- Wir durchlaufen zuerst das numberArray, um Schlüssel / Wert-Paare im located_pairs Objekt zu erstellen. Während dieses Vorgangs wird nach Eindeutigkeit und Duplikaten gesucht.
- Wir laufen dann über die Schlüssel des gefundenen Objekts und prüfen, ob es mit dem Ziel übereinstimmt oder nicht. Wenn dies der Fall ist, wird die Anzahl der Paare erhöht.
