やあ、

一意の値を保存し、値の挿入、値の合計数の検索、値の削除ができるデータ構造をお探しですか?これに最適な選択はセットです。多くのプログラミング言語には Set データ構造が組み込まれており、JavaScript も例外ではありません。セットがどのように機能するかをさらに詳しく見てみましょう。

セットとは何ですか?
Set は、プリミティブ値でもオブジェクト参照でも、あらゆるタイプの一意の値を保存できるデータ構造です。このセットでは、挿入、削除、更新、サイズ変更の操作を O(1) の時間計算量で行うことができます。これにより、設定がより速く効率的に行われます。

セットは、アクセス時間が短縮されるように設計されています。これらは通常、単に各項目を 1 つずつ確認するよりも早く項目を検索できるように実装されています。一般的な実装は、ハッシュ テーブル (O(1) ルックアップ) または検索ツリー (O(log(N)) ルックアップ) です。

キーポイント

• 高速アクセス: セットを使用すると、要素にすばやくアクセスできます。
• 実装: 通常、ハッシュ テーブルまたは検索ツリーを使用して実装されます。
• 検索時間: 平均検索時間は O(N) よりも優れており、多くの場合 O(1) または O(log(N)).

基本的なメソッド

1. add : 設定する要素を追加します。要素がセット内に存在する場合、何も行いません。
2. has : 要素がセット内に存在する場合は true を返し、それ以外の場合は false を返します。
3. size : セットのサイズを返します。
4. delete : セットから要素を削除します。
5. keys : JavaScript Set の .keys() メソッドは、挿入された順序で Set の値を含む新しい反復子オブジェクトを返します。

例

// 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

リートコード問題を含むセットの例:

3.繰り返し文字を含まない最長の部分文字列

文字列 s を指定して、文字を繰り返さない最長の部分文字列の長さを見つけます。

解決

/**
 * @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 



説明： 

関数 lengthOfLongestSubstring は、Set を使用したスライディング ウィンドウ手法を使用して、文字を繰り返さずに最長の部分文字列を検索します。

• ウィンドウを展開: 文字がまだ存在しない場合は、セットに文字を追加します。
• ウィンドウを縮小: 重複が見つかった場合はウィンドウの先頭から文字を削除し、ウィンドウ サイズを調整します。
• 長さの更新: 一意の文字を含む部分文字列の最大長を追跡します。
• このアプローチでは、各文字を最大 2 回処理することで、効率的な O(N) 時間の複雑さを保証します。

以上です。ご不明な点やご提案などがございましたら、お気軽にコメントを追加してください。

出典:
MDN (セット)