Das Sliding-Window-Muster verstehen

Das Sliding-Window-Muster wird verwendet, um die Zeitkomplexität von Problemen zu reduzieren, die Subarrays oder Substrings betreffen. Anstatt für jeden Bereich alles neu zu berechnen, “schieben” wir ein Fenster über die Sammlung und aktualisieren nur die Elemente, die eintreten und austreten.

1. Längster Substring ohne wiederholte Zeichen

Finden Sie die Länge des längsten Substrings, der nur eindeutige Zeichen enthält.

function lengthOfLongestSubstring(s: string): number {
  let start = 0;
  let maxLength = 0;
  const lastSeenMap = new Map<string, number>();

  for (let end = 0; end < s.length; end++) {
    const char = s[end];

    // Wenn wir dieses Zeichen gesehen haben und es innerhalb unseres aktuellen Fensters liegt
    if (lastSeenMap.has(char) && lastSeenMap.get(char)! >= start) {
      // Den Start des Fensters hinter das vorherige Vorkommen verschieben
      start = lastSeenMap.get(char)! + 1;
    }

    lastSeenMap.set(char, end);
    maxLength = Math.max(maxLength, end - start + 1);
  }

  return maxLength;
}

[!TIP] Map vs. Array: Wenn Sie wissen, dass die Eingabe nur ASCII-Zeichen enthält, kann die Verwendung eines Arrays der Größe 128 als Frequenzkarte in JavaScript-Engines etwas schneller sein als ein Map-Objekt.

2. Max Consecutive Ones III

Gegeben ein binäres Array nums und eine Ganzzahl k, geben Sie die maximale Anzahl aufeinanderfolgender 1en zurück, wenn Sie höchstens k Nullen umwandeln können.

function longestOnes(nums: number[], k: number): number {
  let left = 0;
  let zeroCount = 0;
  let maxLength = 0;

  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) {
      zeroCount++;
    }

    // Das Fenster verkleinern, bis wir höchstens k Nullen haben
    while (zeroCount > k) {
      if (nums[left] === 0) {
        zeroCount--;
      }
      left++;
    }

    maxLength = Math.max(maxLength, right - left + 1);
  }

  return maxLength;
}

Wann verwendet man Sliding Window?

1. Zusammenhängende Daten: Sie suchen nach einem Subarray, Substring oder einem Bereich.
2. Optimalität: Sie müssen eine maximale, minimale oder die längste/kürzeste Eigenschaft finden.
3. Lineare Zeit: Sie möchten $O(n^2)$ vermeiden und zielen auf $O(n)$ ab.

[!NOTE] Dynamisches vs. Fixes Fenster:

• Fix: Die Fenstergröße K ist konstant (z.B. “Summe aller 3 Elemente”).
• Dynamisch: Das Fenster wächst oder schrumpft basierend auf einer Bedingung (wie in den obigen Beispielen).

Pro-Interview-Tipp

Wenn Sie gefragt werden, Zeichen in einem Fenster zu verfolgen, sind eine Hash-Map oder ein Frequenz-Array Ihre besten Freunde. Sie ermöglichen es Ihnen, in $O(1)$ zu wissen, ob eine Bedingung erfüllt ist, bevor Sie den “rechten” Pointer erweitern oder den “linken” Pointer verkleinern.