Es geht um Muster!

Sobald Sie die Muster gelernt haben, fühlt sich alles etwas einfacher an! Wenn Sie wie ich sind, mögen Sie wahrscheinlich keine technischen Vorstellungsgespräche, und das kann ich Ihnen nicht verübeln – sie können hart sein.

Array-Probleme gehören zu den häufigsten Problemen, denen Sie in Vorstellungsgesprächen begegnen werden. Diese Probleme betreffen häufig die Arbeit mit natürlichen Arrays:

const arr = [1, 2, 3, 4, 5];

Und String-Probleme, bei denen es sich im Wesentlichen um Arrays von Zeichen handelt:

"mylongstring".split(""); // ['m', 'y', 'l', 'o','n', 'g', 's','t','r','i', 'n', 'g']

Eines der häufigsten Muster zur Lösung von Array-Problemen ist das Schiebefenster.

Schiebefenstermuster

Das Schiebefenstermuster umfasst zwei Zeiger, die sich in die gleiche Richtung bewegen – wie ein Fenster, das über das Array gleitet.

Wann sollte man es verwenden?

Verwenden Sie das Schiebefenstermuster, wenn Sie ein Unterarray oder eine Unterzeichenfolge finden müssen, die eine bestimmte Bedingung erfüllt, z. B. das Minimum, das Maximum, die längste oder kürzeste.

Regel 1: Wenn Sie ein Unterarray oder eine Unterzeichenfolge suchen müssen und die Datenstruktur ein Array oder eine Zeichenfolge ist, sollten Sie die Verwendung des Schiebefenstermusters in Betracht ziehen.

Einfaches Beispiel

Hier ist ein einfaches Beispiel zur Einführung des Konzepts von Zeigern in einem Schiebefenster:

function SlidingWindow(arr) {
    let l = 0;  // Left pointer
    let r = l   1;  // Right pointer

    while (r 



Beachten Sie, dass sich der linke (L) und der rechte (R) Zeiger nicht gleichzeitig bewegen müssen, sondern sich in die gleiche Richtung bewegen müssen.



Der rechte Zeiger wird nie tiefer sein als der linke Zeiger.

Lassen Sie uns dieses Konzept anhand eines echten Interviewproblems untersuchen.


  
  
  Problem aus der realen Welt: Längster Teilstring ohne sich wiederholende Zeichen


Problem: Ermitteln Sie anhand einer Zeichenfolge s die Länge der längsten Teilzeichenfolge ohne sich wiederholende Zeichen.

Schlüsselwörter: sub-Zeichenfolge, längste (maximal)


function longestSubstr(str) {
    let longest = 0;
    let left = 0;
    let hash = {};

    for (let right = 0; right = left) {
            left = hash[str[right]]   1;
        }

        hash[str[right]] = right;
        longest = Math.max(longest, right - left   1);
    }

    return longest;
}




Machen Sie sich keine Sorgen, wenn das kompliziert aussieht – wir gehen es Stück für Stück durch.


let str = "helloworld";
console.log(longestSubstr(str));  // Output: 5




Der Kern dieses Problems besteht darin, die längste Teilzeichenfolge ohne sich wiederholende Zeichen zu finden.


  
  
  Anfangsfenster: Größe 0


Zu Beginn befinden sich sowohl der linke (L) als auch der rechte (R) Zeiger an derselben Stelle:


let left = 0;

for (let right = 0; right 





h e l l o w o r l d 
^
^
L
R




Und wir haben einen leeren Hash (Objekt):


let hash = {};




Was ist das Tolle an Objekten? Sie speichern eindeutige Schlüssel, was genau das ist, was wir brauchen, um dieses Problem zu lösen. Wir verwenden Hash, um alle Charaktere zu verfolgen, die wir besucht haben, und prüfen, ob wir den aktuellen Charakter schon einmal gesehen haben (um Duplikate zu erkennen).

Anhand der Zeichenfolge können wir visuell erkennen, dass „world“ die längste Teilzeichenfolge ohne sich wiederholende Zeichen ist:


h e l l o w o r l d 
          ^        ^   
          L        R




Das hat eine Länge von 5. Wie kommen wir also dorthin?

Lassen Sie es uns Schritt für Schritt aufschlüsseln:


  
  
  Ausgangszustand




hash = {}

h e l l o w o r l d 
^
^
L
R





  
  
  Iteration 1:


Bei jeder Iteration fügen wir das Zeichen unter dem R-Zeiger zur Hash-Map hinzu und erhöhen:


hash[str[right]] = right;
longest = Math.max(longest, right - left   1);




Derzeit gibt es in unserem Fenster keine sich wiederholenden Zeichen (h und e):


hash = {h: 0}
h e l l o w o r l d 
^ ^
L R





  
  
  Iteration 2:




hash = {h: 0, e: 1}
h e l l o w o r l d 
^   ^
L   R




Jetzt haben wir ein neues Fenster: hel.


  
  
  Iteration 3:




hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
^     ^
L     R




Hier wird es interessant: Wir haben bereits l in unserem Hash und R zeigt auf ein weiteres l in der Zeichenfolge. Hier kommt unsere if-Anweisung ins Spiel:


if (hash[str[right]] !== undefined)




Wenn unser Hash den Buchstaben enthält, auf den R zeigt, haben wir ein Duplikat gefunden! Das vorherige Fenster (hel) ist unser bisher längstes.

Also, was machen wir als nächstes? Wir verkleinern das Fenster von links, indem wir den L-Zeiger nach oben bewegen, da wir den linken Teilstring bereits verarbeitet haben. Aber wie weit bewegen wir uns L?


left = hash[str[right]]   1;




Wir verschieben L direkt nach dem Duplikat:


hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
      ^
      ^
      L
      R




Wir fügen unser Duplikat immer noch zum Hash hinzu, sodass L jetzt einen Index von 3 hat.


hash[str[right]] = right;
longest = Math.max(longest, right - left   1);





  
  
  Neuer Zustand: Iteration 4




hash = {h: 0, e: 1, l: 3}
h e l l o w o r l d 
      ^ ^
      L R





  
  
  Iterationen 4 bis 6




hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
      ^     ^
      L     R




Wenn R auf ein anderes Duplikat (o) zeigt, verschieben wir L direkt nach dem ersten o:


hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
          ^ ^
          L R




Wir machen weiter, bis wir auf ein weiteres Duplikat l stoßen:


hash = {h: 0, e: 1, l: 3, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^     ^
          L     R




Beachten Sie jedoch, dass es außerhalb des aktuellen Fensters liegt! beginnend mit w, 


  
  
  Regel 3: Verarbeitetes Sub-X ignorieren


Alles außerhalb des aktuellen Fensters ist irrelevant – wir haben es bereits verarbeitet. Der Schlüsselcode, um dies zu verwalten, ist:


if (hash[str[right]] !== undefined && hash[str[right]] >= left)




Diese Bedingung stellt sicher, dass wir uns nur um Zeichen im aktuellen Fenster kümmern und jegliches Rauschen herausfiltern.


hash[str[right]] >= left




Wir konzentrieren uns auf alles, was größer oder gleich dem linken Zeiger ist


  
  
  Letzte Iteration:




hash = {h: 0, e: 1, l: 8, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^       ^
          L       R




Ich weiß, dass dies ausführlich war, aber die Zerlegung von Problemen in kleinere Muster oder Regeln ist der einfachste Weg, sie zu meistern.


  
  
  Zusammenfassend:

• Regel 1: Schlüsselwörter im Problem (z. B. Maximum, Minimum) sind Hinweise. Bei diesem Problem geht es darum, die längste Teilzeichenfolge ohne sich wiederholende Zeichen zu finden.
• Regel 2: Wenn Sie einzigartige oder sich nicht wiederholende Elemente finden müssen, denken Sie an Hash-Maps.
• Regel 3: Konzentrieren Sie sich auf das aktuelle Fenster – alles außerhalb davon ist irrelevant.

Bonus-Tipps:

• Bröseln Sie das Problem auf und gestalten Sie es ausführlich, indem Sie eine kleine Teilmenge verwenden.
• Überlegen Sie beim Maximieren des aktuellen Fensters, wie Sie es so lang wie möglich machen. Umgekehrt sollten Sie beim Minimieren darüber nachdenken, wie Sie es so klein wie möglich machen können.

Zum Abschluss gibt es hier noch eine kleine Herausforderung zum Ausprobieren! Ich werde meine Lösung in den Kommentaren veröffentlichen – es ist eine großartige Möglichkeit zum Üben.

Problem 2: Summe größer oder gleich dem Ziel

Suchen Sie bei einem gegebenen Array das kleinste Unterarray mit einer Summe, die gleich oder größer als das Ziel ist (meine Lösung wird der erste Kommentar sein).

/**
 * 
 * @param {Array} arr 
 * @param {number} target 
 * @returns {number} - length of the smallest subarray
 */
function greaterThanOrEqualSum(arr, target){
   let minimum = Infinity;
   let left = 0;
   let sum = 0;

   // Your sliding window logic here!
}

Denken Sie daran, wie bei allem beim Programmieren ist Wiederholung der Schlüssel! Es tauchen immer wieder Probleme mit Schiebefenstern auf. Zögern Sie also nicht, weitere Beispiele zu googeln und weiter zu üben.

Ich fasse mich kurz, aber bleiben Sie dran – der nächste Artikel befasst sich mit dem Zwei-Zeiger-Muster und der Rekursion (Vorbereitung auf Baumprobleme). Es wird etwas anspruchsvoller!

Wenn Sie mehr exklusive Inhalte wünschen, können Sie mir auf Twitter oder Ko-fi folgen. Ich werde dort ein paar zusätzliche Dinge posten!

Ressourcen:

Handbuch für technische Interviews

Leet-Code-Arrays 101