So finden Sie sich nicht wiederholende Teilzeichenfolgen in JavaScript

In der tatsächlichen Entwicklung müssen wir häufig einige Operationen und Verarbeitungen an Zeichenfolgen durchführen, darunter das Finden sich nicht wiederholender Teilzeichenfolgen. Beispielsweise ist in der Zeichenfolge „abcabcbb“ die längste sich nicht wiederholende Teilzeichenfolge „abc“ und in der Zeichenfolge „bbbbbb“ ist die längste sich nicht wiederholende Teilzeichenfolge „b“. Diese Probleme sind in Algorithmen als das Problem des „längsten sich nicht wiederholenden Teilstrings“ bekannt und wir können sie mit JavaScript lösen.

1. Gewalttätige Aufzählungsmethode

Die einfachste Methode besteht darin, die Brute-Force-Aufzählungsmethode zu verwenden, d. Notieren Sie dann die Länge der Teilzeichenfolge zu diesem Zeitpunkt, setzen Sie die Teilzeichenfolge zurück und durchlaufen Sie die Zeichenfolge weiter nach unten, bis das Ende der Durchquerung erreicht ist.

Der Code lautet wie folgt:

function longestSubstring(str) {
  let maxLength = 0; // 定义最大长度为 0
  for(let i = 0; i < str.length; i++) {
    let map = new Map(); // 定义 Map 来保存子串中元素出现的次数
    let length = 0; // 定义子串长度为 0
    for(let j = i; j < str.length; j++) {
      if(map.has(str[j])) { // 如果子串中已经有这个元素了
        maxLength = Math.max(maxLength, length); // 更新最大长度
        break; // 说明这个子串已经不符合要求了，跳出内部循环
      } else {
        map.set(str[j], 1); // 在 Map 中记录该元素的出现次数
        length++; // 子串长度 +1
        maxLength = Math.max(maxLength, length); // 更新最大长度
      }
    }
  }
  return maxLength;
}

Die zeitliche Komplexität dieser Methode beträgt O(n^3). Da die Anzahl der verschachtelten Schleifen sehr groß ist, ist ihre Effizienz bei der Verarbeitung längerer Zeichenfolgen sehr ineffizient.

2. Schiebefenstermethode

Um die Effizienz zu verbessern, können wir die Schiebefenstermethode verwenden. Die Idee des Schiebefensters besteht darin, ein Fenster der Länge k beizubehalten und dieses Fenster zu verschieben, um Zeichenfolgen zu verarbeiten. Bei diesem Problem entspricht die Länge des Schiebefensters der Länge der sich nicht wiederholenden Zeichenfolge.

Konkret definieren wir beim Durchlaufen einer Zeichenfolge einen Startzeiger und einen Endzeiger, und diese beiden Zeiger bilden ein Fenster. Wenn in jeder Schleife das Element, auf das der Endzeiger zeigt, nicht im Fenster vorhanden ist, können wir es dem Fenster hinzufügen, dann das Fenster erweitern und die Länge des Fensters aktualisieren. Wenn das Element, auf das der Endzeiger zeigt, bereits im Fenster vorhanden ist, müssen wir den Startzeiger nach rechts verschieben und das Fenster verkleinern, bis das Element, auf das der Endzeiger zeigt, nicht mehr im Fenster vorhanden ist. In diesem Prozess müssen wir eine Zuordnungstabelle verwenden, um die Anzahl der Vorkommen jedes Elements im Fenster aufzuzeichnen.

Der Code lautet wie folgt:

function longestSubstring(str) {
  let maxLength = 0; // 定义最大长度为 0
  let map = new Map(); // 定义 Map 来保存元素出现的次数
  let left = 0; // 定义左指针为 0
  for(let right = 0; right < str.length; right++) {
    if(map.has(str[right])) { // 如果窗口内已经有该元素了
      left = Math.max(left, map.get(str[right]) + 1); // 更新左指针，向右移动
    }
    map.set(str[right], right); // 在 Map 中记录该元素的位置
    maxLength = Math.max(maxLength, right - left + 1); // 更新最大长度
  }
  return maxLength;
}

Die zeitliche Komplexität der Schiebefenstermethode beträgt O(n). Sie verwendet HashMap, um Zeichen schnell zu finden und zu speichern, was schneller und effizienter ist als die Brute-Force-Aufzählungsmethode.

3. Zusammenfassung

Für das Problem mit der längsten sich nicht wiederholenden Teilzeichenfolge in einer Zeichenfolge können wir zwei Methoden verwenden, um es zu lösen: die Brute-Force-Aufzählungsmethode und die Schiebefenstermethode. Die Brute-Force-Aufzählungsmethode weist eine hohe zeitliche Komplexität auf, während die Sliding-Window-Methode effizienter ist. In der tatsächlichen Entwicklung können wir je nach Bedarf die geeignete Methode zur Lösung des Problems auswählen.

Das obige ist der detaillierte Inhalt vonSo finden Sie sich nicht wiederholende Teilzeichenfolgen in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!