Interview-Kit: Arrays – Schiebefenster.

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 oft 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 man es verwendet

Verwenden Sie das Schiebefenstermuster, wenn Sie ein Sub-Array oder eine Sub-String finden müssen, das eine bestimmte Bedingung erfüllt, z. B. das Minimum, das Maximum, die längste usw 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, um das Konzept der Zeiger in einem Schiebefenster vorzustellen:

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

    while (r < arr.length) {
        console.log("left", arr[l]);
        console.log("right", arr[r]);
        l++;
        r++;
    }
}

SlidingWindow([1, 2, 3, 4, 5, 6, 7, 8]);

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

Der rechte Zeiger wird niemals niedriger sein als der linke Zeiger.

Lassen Sie uns dieses Konzept anhand eines echten Interviewproblems untersuchen.

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

Problem:Gegeben eine Zeichenfolge s, ermitteln Sie die Länge der längsten Teilzeichenfolge ohne sich wiederholende Zeichen.

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

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

    for (let right = 0; right < str.length; right++) {
        if (hash[str[right]] !== undefined && hash[str[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 < str.length; right++) {  // RIGHT POINTER

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 Folgendes:

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 R enthält, auf den er verweist, 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 immer noch unser Duplikat 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, lautet:

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

Diese Bedingung stellt sicher, dass wir uns nur um Zeichen innerhalb des aktuellen Fensters 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.

In Summary:

• Rule 1: Keywords in the problem (e.g., maximum, minimum) are clues. This problem is about finding the longest sub-string without repeating characters.
• Rule 2: If you need to find unique or non-repeating elements, think hash maps.
• Rule 3: Focus on the current window—anything outside of it is irrelevant.

Bonus Tips:

• Break down the problem and make it verbose using a small subset.
• When maximizing the current window, think about how to make it as long as possible. Conversely, when minimizing, think about how to make it as small as possible.

To wrap things up, here's a little challenge for you to try out! I’ll post my solution in the comments—it’s a great way to practice.

Problem 2: Sum Greater Than or Equal to Target

Given an array, find the smallest subarray with a sum equal to or greater than the target(my solution will be the first comment).

/**
 * 
 * @param {Array<number>} 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!
}

Remember, like anything in programming, repetition is key! Sliding window problems pop up all the time, so don’t hesitate to Google more examples and keep practicing.

I’m keeping this one short, but stay tuned—the next article will dive into the two-pointer pattern and recursion (prepping for tree problems). It’s going to be a bit more challenging!

If you want more exclusive content, you can follow me on Twitter or Ko-fi I'll be posting some extra stuff there!

Resources:

Tech interview Handbook

leet code arrays 101

Das obige ist der detaillierte Inhalt vonInterview-Kit: Arrays – Schiebefenster.. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!