Leetcode: Zweisummen, ein intuitiver Ansatz

Stellen Sie sich vor, Sie sind der stolze Besitzer eines Souvenirladens im Spot-On Change Hotel. Beim Schließen der Kasse stellen Sie fest, dass 8 Euro zu viel übrig sind. Offenbar hat ein Gast nicht das passende Wechselgeld erhalten. Dies könnte den Ruf des Hotels schädigen. Um dies zu vermeiden, beschließen Sie, das Rätsel des falschen Wechselgelds zu lösen. Beim Öffnen des Kassensystems des Ladens stellen Sie fest, dass der Fehler auf zwei verschiedenen Konten aufgetreten ist!

Sie entwickeln einen Plan: Sie besuchen jedes Zimmer und fragen die Gäste, welches Wechselgeld sie im Laden bekommen haben, bis Sie die beiden mit der falschen Banknote finden. Im ersten Stock angekommen, berichtet ein Gast, dass er 4 Euro Wechselgeld bekommen hat. Sie rechnen aus, dass Sie eine Zahl finden müssen, die zusammen mit den 4 Euro 8 ergibt. Im zweiten Stock hat der Gast 5 Euro Wechselgeld. 4 + 5 ergibt 9, also kann es nicht dieser sein … Fünfter Stock, sechster … Zehnter, NEIN, NEIN, NEIN!

Da du den Wert beim ersten Versuch nicht gefunden hast, gehst du in den zweiten Stock und beginnst dort erneut, alle Gäste nach ihrem Wechselgeld zu fragen, um es mit dem Wert aus dem nächsten Startstockwerk vergleichen zu können. Anstrengend, oder? In der Informatik nennt man diese Suchmethode Brute Force, eine extrem langsame Suchmethode, die funktioniert, indem ein Element mit den folgenden im Array verglichen wird.

Dies ist sehr zeitaufwendig und nicht effizient. Stellen Sie sich vor, Sie müssten alle Stockwerke des Spot-On Change Hotels mehrmals auf und ab gehen! Das ist weder für Sie noch für den Computer praktisch.

Wenn Sie neugierig sind, wie dieses Auf- und Abfahren der Stockwerke in einem Softwareprogramm aussehen würde, würde es in JavaScript so aussehen:

 twoSum(nums, target) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] === target) { return [i, j]; } } } }

Nachdem Sie die Situation in Ruhe beurteilt haben, wird Ihnen klar, dass es einen effizienteren Weg gibt, die beiden Gäste mit dem falschen Wechselgeld zu finden.

Sie verfeinern Ihre anfängliche mathematische Intuition, dass 9 Euro x + y entsprechen. Mit ein wenig Arithmetik stellen Sie fest: x + y = 9 ist dasselbe wie y = 9 – x, und das macht den entscheidenden Unterschied bei der Steigerung der Effizienz Ihrer Suche.

Eine weitere Änderung Ihrer Strategie besteht darin, dass Sie jetzt einen Notizblock mitnehmen und die Werte aufschreiben, die Ihnen die Gäste nennen. So müssen Sie die Gäste nicht zweimal nach demselben Wert fragen und Sie müssen nicht den ganzen Tag Treppen rauf- und runtergehen. (Was für ein schrecklicher Zeitpunkt, wenn der Aufzug kaputt gehen könnte!).

Mit den neuen Werkzeugen in der Hand gehen Sie in den ersten Stock, wo Ihnen ein Gast mitteilt, dass er 5 Euro Wechselgeld hat. Sie notieren dies als {5: 0}, was einem Wert von 5 an Position 0 entspricht. Wenn Sie in der Gleichung x durch 5 ersetzen, berechnen Sie y = 8–5, was zu y = 3 führt. Da Ihr Notizblock noch leer ist, haben Sie die Zahl 3 nicht notiert, die die Komplementärzahl zu 5 wäre, um das Ergebnis 8 zu erhalten. Anschließend notieren Sie die Zahl 5 in Ihrem Notizblock (denken Sie daran, immer die im Moment überprüfte Zahl und nicht ihr Komplement aufzuschreiben; Sie verwenden das Komplement nur, um es mit der aufgeschriebenen Zielzahl zu vergleichen). Sie gehen zum zweiten Gast, der erwähnt, 2 Euro Wechselgeld erhalten zu haben. Indem Sie die Formel erneut anwenden: y = 8–2 => y = 6, überprüfen Sie Ihre Aufzeichnung, in der Sie keine Zahl 6 finden. Daher fügen Sie Ihrer Aufzeichnung die 2 hinzu, die nun als {5: 0, 2: 1} vorliegt. Bei der weiteren Suche meldet der nächste Gast, dass er 3 Euro Wechselgeld bekommen hat. Sie rechnen erneut: y = 8–3 => y = 5. Bingo! Sie haben eine 5 auf Ihrem Notizblock notiert! Der Gast aus Etage 0 ist komplementär zu dem aus Etage 2! Diese Vorgehensweise wird als Hash-Tabelle bezeichnet und ist sowohl für Sie als auch für den Computer viel schneller und effizienter. In JavaScript würde dies wie folgt implementiert:

 twoSum(nums, target) { const myTable = {}; for (let i = 0; i < nums.length; i++) { const complementaryNumber = target - nums[i]; if (complementaryNumber in myTable) { return [i, myTable[complementaryNumber]]; } myTable[nums[i]] = i; } }

Dies ist ein einfaches Problem von Leetcode , das erst einfach wird, wenn Sie die Konzepte dahinter verstehen. Ich empfehle, dass Sie versuchen, das Problem selbst zu lösen und einige Zeit damit verbringen, eine Intuition dahinter zu entwickeln, Ihre eigene Analogie zu erstellen, zu überprüfen und zu versuchen, Pseudocode zu schreiben, bevor Sie mit der Lösung fortfahren.

Ich hoffe, meine Analogie hat Ihnen geholfen, die Konzepte hinter der Zweisummen-Herausforderung besser zu verstehen.

Bis zum nächsten Mal!