セットとは何か、そしてそれはどのような問題を解決するのか？

Question

Accepted Answer

**セット**は、**ユニークな**要素の順序なしコレクションです。その核となる力は、「Xがここに含まれているか?」という問いに**平均O(1)**で答えることができ、自動的に重複を拒否することです。

## 例

```python
seen = set()
seen.add('a')
seen.add('a')          # ignored — already present
print(len(seen))       # 1
'a' in seen            # O(1) average membership test

# Set algebra
a = {1, 2, 3}
b = {2, 3, 4}
a & b                  # intersection -> {2, 3}
a | b                  # union        -> {1, 2, 3, 4}
a - b                  # difference   -> {1}
```

ほとんどのセットは**ハッシュセット**(キーのみを格納するハッシュテーブル)として実装されているため:

| 操作 | 平均 |
|---|---|
| add | O(1) |
| remove | O(1) |
| メンバーシップ (`in`) | O(1) |

## 一般的な用途

- **重複排除** — リストから繰り返しを1行で削除する。
- **高速メンバーシップ判定** — 「これまでこれを見たことがあるか?」
- **関係性** — グループ間の交差/和集合/差集合。

## なぜ重要なのか

セットは「ユニークさ」と「メンバーシップ」を自明かつ高速にしており、リスト上の遅いネストされたループを置き換えます。

一般的なインタビューの罠 — 重複の検出またはアクセス済みノードの検出 — は数個のセット操作に縮小されます。