XOR（排他的論理和）を使った1パス走査で O(n)時間・O(1)空間 を実現
💡 一言で言うと：「配列の中でペアを組んでいない、1回だけ登場する数字を見つける問題」
💡 この問題を一言で言うと：「配列の中でペアを組んでいない、1回だけ登場する数字を見つける問題」
配列
nums
の要素はほとんどが2回ずつ登場し、1つだけ1回しか登場しない要素が混ざっています。それを効率よく見つけ出すのがゴールです。
⚠️ なぜ単純な方法では解けないのか
nums = [2, 2, 1]
出力: 1
2は2回登場して打ち消し合うため、1回しか登場しない1が答えになります。
nums = [4, 1, 2, 1, 2]
出力: 4
1と2はそれぞれ2回登場して打ち消し合うため、1回しか登場しない4が答えになります。このページのステップ解説では、この例を使って動作を追跡します。
入力例
nums = [4, 1, 2, 1, 2]
を使って、result 変数がどう変化していくかを1ステップずつ確認しましょう。
📋 このコードの構造（先に全体像を把握しよう）
from __future__ import annotations
from typing import List
class Solution:
"""
136. Single Number 解決クラス
配列内で1回だけ登場する数値を、XOR（排他的論理和）を使って
O(n)時間・O(1)空間で見つける。
"""
def singleNumber(self, nums: List[int]) -> int:
"""
配列内で1回だけ登場する数値を返す。
Args:
nums: 1回だけ登場する要素が1つ含まれる整数配列。
それ以外の要素はすべてちょうど2回登場する。
Returns:
1回だけ登場する整数。
Raises:
TypeError: nums がリストでない、または要素に int 以外が含まれる場合。
ValueError: nums が空の場合。
"""
# isinstance() で型チェックする。
# Python は動的型付け（＝実行するまで型が確定しない仕組み）のため、
# 呼び出し元が誤った型を渡しても実行時まで気づけない。
if not isinstance(nums, list):
raise TypeError("Input must be a list")
# all() + ジェネレータ式で全要素が int かどうかを1行でチェックする。
if not all(isinstance(x, int) for x in nums):
raise TypeError("All elements must be integers")
# 制約上は長さ1以上が保証されているが、防御的プログラミングとして
# 空リストを明示的に弾いておく。
if len(nums) == 0:
raise ValueError("Input list must not be empty")
# result を「これまでXORを重ねた累積値」として使う。
# 初期値を 0 にするのは、0 ^ a = a という性質があるため。
result: int = 0
# 配列を1回だけ走査し、各要素を result に XOR で重ねていく。
# 同じ数字が2回現れると a ^ a = 0 で打ち消し合い、
# 最終的にペアのない「はぐれ者」の数字だけが result に残る。
for num in nums:
result ^= num
return result
▶ 入力例 nums = [4, 1, 2, 1, 2] での動作トレース
初期状態: result = 0 num = 4 → result = 0 ^ 4 = 4 num = 1 → result = 4 ^ 1 = 5 num = 2 → result = 5 ^ 2 = 7 num = 1 → result = 7 ^ 1 = 6 (1が2回目 → 打ち消し合いの途中経過) num = 2 → result = 6 ^ 2 = 4 (2が2回目 → 打ち消し合い完了) 走査終了 → result = 4 を返す
🗺️ フローチャートの読み方
🔎 入力例 nums = [4, 1, 2, 1, 2] でのフロー追跡
フローの説明：
このアルゴリズムは「検証 → 初期化 →
ループ」というシンプルな3段構成です。ループ部分だけが配列の要素数に応じて繰り返され、それ以外は1回きりの処理です。ループが要素数分だけ回ることが、時間計算量がO(n)になる直接の理由です。
📖 Big-O 記法の読み方（入力サイズ n が大きくなるにつれて処理時間がどう増えるかの目安）
| アプローチ | 時間 | 空間 | 備考 |
|---|---|---|---|
| Counterで出現回数を数える | O(n) | O(n) | 追加メモリが制約に違反 |
| sortedで隣同士を比較 | O(n log n) | O(n) | ソート自体が線形時間の制約に違反 |
| XOR + forループ（採用） | O(n) | O(1) | 制約に完全一致・可読性も高い |
| XOR + functools.reduce | O(n) | O(1) | 競技プログラミング向けの簡潔版 |
🔍 なぜこの計算量になるのか
配列を1回だけ走査するため、時間計算量はO(n)になります。XORの結果を保持する result という変数1つしか使わないため、空間計算量は入力サイズに関係なく常にO(1)です。ハッシュテーブルを使う方法はO(n)の追加メモリを必要とし、ソートを使う方法はO(n log n)の時間がかかるため、この問題の制約（線形時間・定数空間）を同時に満たせるのはXOR方式だけです。
このページで登場した専門用語をまとめました。分からない言葉が出てきたときに参照してください。
def f(x: int) -> str:
のように書く。pylanceのような静的解析ツールがバグを実行前に検出できるようになる。
dict や
Counter
がこれに相当する。