Available inGermanEnglishFrenchHindiPortugueseRussianSpanish
Coding-Interview-Muster (Blind 75)
Lies ein unbekanntes Blind-75-Problem, benenne die passende Technik und die Invariante, die sie korrekt macht — noch bevor du eine Zeile Code schreibst. Für alle, die siebzig oder mehr LeetCode-Aufgaben gelöst haben und bei einer neuen Aufgabenstellung trotzdem blockieren; Big-O-Sicherheit wird vorausgesetzt, Syntax wird nicht gelehrt. Vierundsechzig Karten ordnen zehn Technik-Familien den Aufgaben zu, die sie brauchen.
Sortiertes Array, zwei Einträge mit gegebener Zielsumme, O(1) Extraspeicher. Welche Technik meint diese Formulierung?
Two Pointers, die von beiden Enden aufeinander zulaufen
— Die Sortierung erledigt hier die Arbeit einer Hash Map.
Source
Drei Hinweise kommen zusammen: Die Eingabe kommt sortiert, gesucht ist ein Paar, und die Speichergrenze verbietet die Hash Map. Setz je einen Index an ein Ende; ist die Summe zu groß, rückt der rechte nach innen, ist sie zu klein, der linke. Jeder Schritt erledigt einen Index endgültig, also O(n) ohne Zusatzspeicher. Im Raum fällt der Name englisch: „two pointers“, und der Zusatz „O(1) extra space“ ist genau die Zeile, die dir die Hash Map wegnimmt. Häufig verwechselt mit: der Hash Map in einem Durchlauf — richtig, wenn das Array unsortiert ist und Speicher frei, weil Sortieren dort ein unnötiges O(n log n) kostet.