Hallo,

Suchen Sie nach einer Datenstruktur, die eindeutige Werte speichert, es Ihnen ermöglicht, Werte einzufügen, die Gesamtzahl der Werte zu ermitteln und Werte zu löschen? Die perfekte Wahl dafür ist ein Set. Viele Programmiersprachen verfügen über eine integrierte Set-Datenstruktur, und JavaScript bildet da keine Ausnahme. Lassen Sie uns tiefer in die Funktionsweise von Sets eintauchen.

Was ist Set?
Das Set ist eine Datenstruktur, mit der Sie eindeutige Werte jeglicher Art speichern können, unabhängig davon, ob es sich um Grundwerte oder Objektreferenzen handelt. Der Satz ermöglicht Einfüge-, Lösch-, Aktualisierungs- und Größenoperationen mit einer Zeitkomplexität von O(1). Dadurch wird die Einstellung schneller und effizienter.

Sets sind so konzipiert, dass sie schnelle Zugriffszeiten ermöglichen. Sie werden in der Regel so implementiert, dass das Nachschlagen von Elementen schneller erfolgt, als einfach jedes Element einzeln zu überprüfen. Die typische Implementierung kann eine Hash-Tabelle (O(1)-Suche) oder ein Suchbaum (O(log(N))-Suche) sein.

Wichtige Punkte

• Schnellzugriff: Sets bieten schnellen Zugriff auf Elemente.
• Implementierung: Wird normalerweise mithilfe von Hash-Tabellen oder Suchbäumen implementiert.
• Suchzeit: Die durchschnittliche Suchzeit ist besser als O(N), häufig O(1) oder O(log(N)).

Grundlegende Methoden

1. add: Es wird ein Element zum Satz hinzugefügt. Wenn das Element im Set vorhanden ist, hat es keine Auswirkung.
2. has: Es wird „true“ zurückgegeben, wenn das Element in der Menge vorhanden ist, andernfalls „false“.
3. size: Gibt die Größe des Sets zurück.
4. delete: Das Element wird aus der Menge entfernt.
5. keys: Die .keys()-Methode in einem JavaScript-Set gibt ein neues Iteratorobjekt zurück, das die Werte des Sets in der Reihenfolge enthält, in der sie eingefügt wurden.

Beispiele

// 1. Create a new Set and use the .add() method to add elements
const mySet = new Set();
mySet.add(10);
mySet.add(20);
mySet.add(30);

console.log(mySet); // Output: Set { 10, 20, 30 }

// 2. Check if the Set has a specific element using .has() method
console.log(mySet.has(20)); // Output: true
console.log(mySet.has(40)); // Output: false

// 3. Delete an element from the Set using .delete() method
mySet.delete(20);
console.log(mySet); // Output: Set { 10, 30 }

// 4. Iterate over the Set using .keys() method
// In Sets, .keys() and .values() do the same thing
for (const key of mySet.keys()) {
  console.log(key);
}
// Output:
// 10
// 30

// 5. Get the size of the Set using .size property
console.log(mySet.size); // Output: 2

Beispiel für einen Satz mit Leetcode-Problem:

3. Längster Teilstring ohne sich wiederholende Zeichen

Ermitteln Sie bei einer gegebenen Zeichenfolge s die Länge der längsten Teilzeichenfolge ohne sich wiederholende Zeichen.

Lösung

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let set = new Set();
    let ans = 0;
    let s_index = 0;
    for (let i = 0; i 



Erläuterung: 

Die Funktion lengthOfLongestSubstring verwendet eine Schiebefenstertechnik mit einem Set, um den längsten Teilstring ohne sich wiederholende Zeichen zu finden:

• Fenster erweitern: Fügen Sie Zeichen zum Set hinzu, wenn sie noch nicht vorhanden sind.
• Fenster verkleinern: Entfernen Sie Zeichen vom Anfang des Fensters, wenn Duplikate gefunden werden, und passen Sie die Fenstergröße an.
• Länge aktualisieren: Verfolgen Sie die maximale Länge der Teilzeichenfolge mit eindeutigen Zeichen.
• Der Ansatz gewährleistet eine effiziente O(N)-Zeitkomplexität, indem jedes Zeichen höchstens zweimal verarbeitet wird.

Das war's. Wenn Sie Zweifel, Vorschläge oder ähnliches haben, können Sie gerne Kommentare hinzufügen.

Quellen:
MDN (Set)