Two Pointers：遅いポインターと速いポインター
slow-fastポインターパターンを使って、in-placeでの重複削除、ゼロの移動、ピボット値を基準にした配列の分割を行います。
「Two Pointers：遅いポインターと速いポインター」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
スロー・ファストポインタの解説
スロー・ファストポインタパターン（tortoise-and-hare とも呼ばれます）は、同じシーケンス上を異なる速度で進む2つのポインタを使います。両端から進めるポインタとは異なり、どちらも先頭から開始します。slow ポインタは一度に1ステップ進み、fast ポインタは2ステップ（またはそれ以上）進みます。速度の差によって有用な不変条件が生まれます。slow ポインタは「有効な接頭辞」を追跡し、fast ポインタは先の条件を調べます。
# Slow pointer marks the write position;
# Fast pointer scans for next non-duplicate.
def remove_duplicates(nums):
if not nums: return 0
slow = 0 # next position to write a unique value
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1 # new length
nums = [1, 1, 2, 3, 3, 3, 4]
k = remove_duplicates(nums)
print(nums[:k]) # [1, 2, 3, 4]ソート済み配列から重複を削除する
ソート済み配列では、重複する値は隣接しています。slow ポインタは、書き込んだ最後の一意な値を追跡し、fast ポインタは先を調べます。fast ポインタが nums[slow] と異なる値に到達したら、slow を進めて新しい値をコピーします。このインプレースアルゴリズムは、追加領域 O(1) で O(n) 時間で実行できます。これは、読み取り・書き込みポインタのパターンの習熟度を問う、面接でよく出る問題です。
def remove_duplicates_v2(nums):
slow = 0
for fast in range(len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
# Allow at most 2 occurrences
def remove_duplicates_k2(nums):
slow = 0
for fast in range(len(nums)):
if slow < 2 or nums[fast] != nums[slow - 2]:
nums[slow] = nums[fast]
slow += 1
return slow
print(remove_duplicates_k2([1,1,1,2,2,3]))
# Result: 5, nums[:5] = [1,1,2,2,3]スロー・ファストでゼロを移動する
ゼロ以外の要素の相対的な順序を保ちながら、すべてのゼロを末尾に移動します。slow ポインタは、ゼロ以外の要素を置く次の位置を示します。fast ポインタはゼロ以外の値を探します。fast がそのような値を見つけたら、slow の位置にコピーして両方を進めます。走査後、slow から末尾までの位置をゼロで埋めます。計算量は O(n) 時間、O(1) 空間です。
def move_zeroes(nums):
slow = 0 # next position for a non-zero
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow] = nums[fast]
slow += 1
# Fill rest with zeroes
while slow < len(nums):
nums[slow] = 0
slow += 1
nums = [0, 1, 0, 3, 12]
move_zeroes(nums)
print(nums) # [1, 3, 12, 0, 0]ピボットを基準に配列を分割する
クイックソートの分割ステップでは、インプレースで要素を並べ替え、pivot 未満のすべての値が pivot 以上の値より前に来るようにします。Lomuto スキームでは、small 要素の最後の位置を示す slow ポインタと、前方を走査する fast ポインタを使います。fast が small 要素を見つけたら、slow を増やして交換します。計算量は O(n) 時間、追加領域 O(1) です。
def lomuto_partition(nums, low, high):
pivot = nums[high]
slow = low - 1 # last position of small element
for fast in range(low, high):
if nums[fast] <= pivot:
slow += 1
nums[slow], nums[fast] = nums[fast], nums[slow]
# Place pivot in final position
nums[slow+1], nums[high] = nums[high], nums[slow+1]
return slow + 1 # pivot's final index
arr = [3, 1, 4, 1, 5, 9, 2, 6]
p = lomuto_partition(arr, 0, len(arr)-1)
print(arr) # elements before p are <= pivot連結リストの中央を見つける
連結リストでスロー・ファストポインタを使うと、fast ポインタは1ステップで2ノード進み、slow ポインタは1ノード進みます。fast が末尾に到達したとき、slow は中央にあります。この O(n) の一回走査による方法は、ノード数を数えてから中央まで移動するよりもはるかに簡潔です。連結リストのマージソートや、連結リストが回文かどうかの判定におけるサブステップとして使われます。
class Node:
def __init__(self, val, nxt=None):
self.val = val
self.next = nxt
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # slow is at middle
# Build 1->2->3->4->5
h = Node(1, Node(2, Node(3, Node(4, Node(5)))))
mid = find_middle(h)
print(mid.val) # 3 (middle of 5 nodes)循環検出：Floydのトータスとヘア
Floydの循環検出では、連結リストの先頭に slow ポインタと fast ポインタを置きます。slow は1ノード、fast は2ノード進みます。循環が存在すると、fast ポインタはいずれ slow ポインタに追いついて循環内部で出会います。fast が None に到達した場合、循環はありません。各反復で fast は slow より1ステップ多く進むため、出会うことが保証されます。長さ k の循環では、slow が循環に入ってから k ステップ以内に出会います。
class ListNode:
def __init__(self, val=0, nxt=None):
self.val = val
self.next = nxt
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # identity check (same object)
return True
return False
# 1->2->3->4->2 (cycle at node 2)
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n1.next=n2; n2.next=n3; n3.next=n4; n4.next=n2
print(has_cycle(n1)) # True循環の開始点を見つける
循環を検出した後（slow == fast）、一方のポインタを head に戻します。その後、両方のポインタを1ステップずつ進めます。両者は循環の開始点で出会います。これは、head から循環の開始点までの距離と、出会った位置から循環の開始点までの距離が、循環の長さを法として等しいという数学的性質を利用しています。これは美しい数学的結果であり、難易度の高い面接問題に頻繁に登場します。
def detect_cycle(head):
slow = fast = head
# Phase 1: detect
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None # no cycle
# Phase 2: find entry
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow # cycle entry node
# Using same cycled list as previous scene
print(detect_cycle(n1).val) # 2 (cycle entry)ハッピー数にスロー・ファストを使う
スロー・ファストポインタは、連結リスト以外にも、循環するあらゆるプロセスに適用できます。「ハッピー数」は各桁の二乗和を繰り返す過程で循環します。n がハッピー数でない場合、数列はいずれループします。slow（1ステップは1回の各桁の二乗和）と fast（2ステップ）でループを検出します。1 で出会えば n はハッピー数であり、それ以外の場合は 1 ではない循環に閉じ込められています。これは、値からなる仮想的な連結リストに Floyd のアルゴリズムを適用したものです。
def is_happy(n):
def next_val(x):
total = 0
while x:
x, d = divmod(x, 10)
total += d * d
return total
slow = n
fast = next_val(n)
while fast != 1 and slow != fast:
slow = next_val(slow)
fast = next_val(next_val(fast))
return fast == 1
print(is_happy(19)) # True (1->9->...->1)
print(is_happy(2)) # False (enters a cycle)リスト末尾から n 番目のノード
2つのポインタを使うと、連結リストを一回だけ走査して末尾から n 番目のノードを見つけられます。まず fast ポインタを n ステップ先に進めます。次に、fast が末尾に到達するまで両方のポインタを同時に進めると、slow は末尾から n 番目のノードを指します。このノードを削除するには、slow の1つ前を指す 'prev' ポインタを保持します。これは、最初に全体の長さを数える必要がない、連結リストの一回走査による典型的な問題です。
def remove_nth_from_end(head, n):
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
# Advance fast n+1 steps
for _ in range(n + 1):
fast = fast.next
# Advance together
while fast:
slow = slow.next
fast = fast.next
# slow.next is the nth from end
slow.next = slow.next.next
return dummy.next
# Build 1->2->3->4->5, remove 2nd from end
h2 = ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))
result = remove_nth_from_end(h2, 2)
# Should give 1->2->3->5文字列問題でのスロー・ファスト
スロー・ファストの考え方は、配列や文字列の問題にも適用できます。ランレングス符号化された文字列を圧縮するとき、slow ポインタは書き込み位置を示し、fast ポインタは各ランの末尾まで走査します。ラン内のすべての文字が slow の文字と等しい場合は fast を進め、それ以外の場合はそのランを記録して slow を更新します。これにより、O(1) 空間で一回の走査による O(n) の処理を実現できます。
def compress(chars):
slow = fast = 0
while fast < len(chars):
char = chars[fast]
count = 0
# Count the run
while fast < len(chars) and chars[fast] == char:
fast += 1
count += 1
chars[slow] = char
slow += 1
if count > 1:
for c in str(count):
chars[slow] = c
slow += 1
return slow
chars = list('aabcccccaa')
print(compress(chars)) # 6
print(chars[:6]) # ['a','2','b','c','5','a']... wait
# Actually: ['a','2','b','c','5','a','2']スロー・ファストと両端からのポインタの使い分け
両端から進めるポインタは、合計が target になるペア、回文の検査、または両側から範囲を狭める問題で使います。スロー・ファストポインタは、書き込み用ポインタが必要な場合（要素の削除や移動）、連結リストの構造を処理する場合（中央や循環）、または任意の値のシーケンスで循環を検出する場合に使います。どちらもネストしたループをなくして O(n) を実現します。決め手になるのは走査の構造です。
# Pattern matcher:
# 1. Sorted array, target sum -> OPPOSITE ENDS
# 2. Remove/filter elements in-place -> SLOW-FAST (read-write)
# 3. Linked list middle/cycle -> SLOW-FAST (1x vs 2x speed)
# 4. Detect cycle in value sequence -> SLOW-FAST (Floyd)
# Example: given sorted array, remove val in-place
def remove_sorted(nums, val):
slow = 0
for fast in range(len(nums)):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
return slow
nums = [0,1,2,2,3,0,4,2]
print(remove_sorted(nums, 2)) # 5理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認します。
レッスンのまとめ
このレッスンでは、スロー・ファスト（読み取り・書き込み）パターンによって、書き込み用ポインタを次の有効な位置に保ちながら fast ポインタが前方を走査し、インプレースでの削除、重複除去、ゼロの移動を支える基本となること、Floydのトータスとヘアは、2つのポインタの速度差を利用して、O(n) 時間かつ O(1) 空間で循環を検出すること、そして循環を検出した後、一方のポインタを head に戻して両方を同じ速度で進めると、証明可能な距離の等式によって循環の開始点が見つかることを学びました。次は、面接で使う Python の文字列 API について学びます。
よくある質問
「Two Pointers：遅いポインターと速いポインター」レッスンは無料ですか？
はい。「Two Pointers：遅いポインターと速いポインター」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「Two Pointers：遅いポインターと速いポインター」で何を学びますか？
slow-fastポインターパターンを使って、in-placeでの重複削除、ゼロの移動、ピボット値を基準にした配列の分割を行います。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「Two Pointers：遅いポインターと速いポインター」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 配列の基礎とin-place操作
- 累積和とランニングトータル
- Two Pointers：両端から近づける
- Two Pointers：遅いポインターと速いポインター