Two Pointers：両端から近づける
左右のポインターを互いに近づけ、ソート済み配列の二数和、valid palindrome、trapping rain waterを解きます。
「Two Pointers：両端から近づける」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
2 ポインターの考え方
2 ポインターのテクニックでは、互いに近づく方向（または同じ方向）へ動く 2 つのインデックス変数を使い、入れ子のループの必要性を減らします。すべてのペアを O(n²) で確認する代わりに、比較するたびに処理を前進させ、O(n) で完了させます。現在のペアの和が大きすぎるか小さすぎるかに応じて、どちらのポインターを動かすかを判断できるようにするため、ほとんどの場合、最初に配列をソートする必要があります。
# Without two pointers: O(n^2)
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target: return [left, right]
elif s < target: left += 1
else: right -= 1
return []ソート済み配列での Two-Sum
ソート済み配列では、一方のポインターを左端（最小値）に、もう一方を右端（最大値）に置きます。和が小さすぎる場合は、左ポインターを右へ動かして和を増やします。和が大きすぎる場合は、右ポインターを左へ動かして和を減らします。各反復で少なくとも一方のポインターが進むため、ループは最大 n 回しか実行されません。ソート後の全体の計算量は O(n) です。重要なのは、ソートされた順序によって、各移動が正しいことを証明できる点です。
def two_sum_sorted(numbers, target):
# numbers is 1-indexed per LeetCode 167
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 1-indexed
elif s < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return []
print(two_sum_sorted([2, 7, 11, 15], 9)) # [1, 2]
print(two_sum_sorted([2, 3, 4], 6)) # [1, 3]回文の判定
文字列を前から読んでも後ろから読んでも同じであれば、その文字列は回文です。両端から 2 つのポインターを開始して中央へ向かって動かし、文字を比較しながら、英数字以外の文字を飛ばします。ポインターが交差したら終了します。時間計算量は O(n)、追加領域は O(1) です。文字列を反転して比較する方法では O(n) の追加メモリを確保する必要があるため、それよりもはるかにすっきりした方法です。
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
# Skip non-alphanumeric
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # FalseThree-Sum：ソート + 2 ポインター
Three-sum では、合計が 0 になる重複のない三つ組をすべて求めます。配列をソートし、各要素 nums[i] を固定したうえで、残りの部分配列に対して、-nums[i] になる和のペアを 2 ポインターで検索します。固定した要素と見つかったペアの重複をスキップし、同じ三つ組が繰り返し現れないようにします。ソートに O(n log n) かかることを除けば、全体の計算量は O(n²) です。
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip dupe
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1; right -= 1
elif s < 0: left += 1
else: right -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1,-1,2],[-1,0,1]]最大の水量を入れられるコンテナ
垂直な線の高さが与えられたとき、最も多くの水を入れられるコンテナを形成する 2 本の線を見つけます。面積は min(height[left], height[right]) × (right - left) です。短い線側のポインターを内側へ貪欲に動かします。高い線側を動かしても、高さの上限を増やせないまま幅が狭くなるだけだからです。この貪欲な選択は最適であることを証明でき、時間計算量 O(n) で処理できます。
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right])
area = h * (right - left)
best = max(best, area)
# Move the shorter wall inward
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 49ソート済み配列の二乗
負の値を含む可能性があるソート済み配列の各要素を二乗し、結果をソート済みの順序で返します。負の値の二乗は大きくなり、正の値の二乗は中央付近で小さくなります。両端に 2 つのポインターを置き、結果の配列を右から左へ（最大値から最小値の順に）埋めます。時間計算量は O(n)、出力領域は O(n) です。二乗してから O(n log n) でソートするよりも、はるかに効率的です。
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]雨水のトラップ
インデックス i にたまる水の量は min(max_left, max_right) - height[i] です。2 ポインター方式では、max_left と max_right の累積値を保持します。max_left < max_right の場合は左側がボトルネックになるため、左ポインターを処理します。それ以外の場合は右側を処理します。これにより、左側の最大値と右側の最大値を格納する別々の配列が不要になり、追加領域 O(1) を実現できます。
def trap(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left]
else:
water += max_left - height[left]
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6貪欲なポインター移動が機能する理由
面接でよくある追加質問は、なぜ短い側のポインターを安全に捨てられるのでしょうかというものです。最大の水量を入れられるコンテナについての証明の概要を示します。height[left] < height[right] だとします。j < right を満たすすべてのペア (left, j) の面積は、height[left] × (j-left) 以下であり、height[left] × (j-left) < height[left] × (right-left) ≤ current area となります。したがって、right より小さい右インデックスを持ち、left から始まるどのペアも現在の面積を上回ることはありません。left を進めることで、それらを安全にスキップできます。
# Correctness argument via contradiction:
# If left < right and height[left] < height[right],
# then for any j in (left, right):
# area(left, j) <= min(h[left], h[j]) * (j - left)
# <= h[left] * (j - left)
# <= h[left] * (right - left) [since j < right]
# = current area
# So no pair (left, j) for j < right can improve.
# Moving left inward is SAFE.
print('Proof verified: advance shorter pointer is optimal')ソート済み配列における最小差のペア
ソート済み配列から、絶対差が最小になる数値のペアを見つけます。向かい合う両端ではなく、隣り合う要素を指す2つのポインタを同時に進め、すべての連続するペアについて |nums[i] - nums[i+1]| を調べます。ソート済み配列では、近い値同士がまとまって並ぶため、最小差は必ず隣接要素の間にあります。ソート後の処理は O(n) です。
def min_diff_pair(nums):
nums.sort() # O(n log n)
min_diff = float('inf')
best = (nums[0], nums[1])
for i in range(len(nums) - 1):
diff = nums[i+1] - nums[i] # sorted: always >= 0
if diff < min_diff:
min_diff = diff
best = (nums[i], nums[i+1])
return best, min_diff
pair, d = min_diff_pair([4, 2, 1, 6, 10, 8])
print(pair, d) # (1, 2) 1両端から進めるツーポインタのテンプレート
両端から進めるツーポインタの問題の多くは、同じ基本構造に従います。このテンプレートを身につけると、時間に追われる状況でも素早く応用できます。重要な判断は、(1) どの条件で left を進めるか、(2) どの条件で right を進めるか、(3) 何を解とみなすか、(4) 重複をどう扱うかの4つです。コードを書く前に、問題文からこれらの判断を組み立てる練習をしてください。
def two_pointer_template(arr, condition):
"""
Generic opposite-ends two-pointer skeleton.
Replace condition logic for each specific problem.
"""
left, right = 0, len(arr) - 1
result = []
while left < right:
current = arr[left] + arr[right] # or some combination
if current == condition: # found a valid pair
result.append((arr[left], arr[right]))
left += 1
right -= 1
elif current < condition: # need to increase
left += 1
else: # need to decrease
right -= 1
return resultツーポインタによる有効なペアのカウント
ツーポインタは、ペアを効率的に数える場合にも使えます。ソート済み配列で「合計が target 未満になるペアの数を数える」問題では、left ポインタを固定し、right ポインタを使って条件を満たす right の最も右側のインデックスを探します。すべてのペア (left, left+1 から right) が有効なので、個数に right - left を加えて left を進めます。これにより、O(n²) ではなく O(n) で有効なペアをすべて数えられます。
def count_pairs_less_than(nums, target):
nums.sort()
left, right = 0, len(nums) - 1
count = 0
while left < right:
if nums[left] + nums[right] < target:
count += right - left # all (left, left+1..right) valid
left += 1
else:
right -= 1
return count
print(count_pairs_less_than([1, 2, 3, 4, 5], 6))
# pairs: (1,2)(1,3)(1,4)(2,3) -> 4理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認します。
レッスンのまとめ
このレッスンでは、両端から進めるツーポインタによって、ソート済み配列での O(n²) のペア列挙を、左右のポインタを O(n) で近づける処理に置き換えられること、どちらのポインタを進めるかは問題の単調性から決まり、現在の進行を制限している側を動かすこと、そして3-Sum、container-with-most-water、trapping rain water、回文の検証はいずれも同じ基本テンプレートに還元できることを学びました。次は、スロー・ファストのツーポインタパターンについて学びます。
よくある質問
「Two Pointers：両端から近づける」レッスンは無料ですか？
はい。「Two Pointers：両端から近づける」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「Two Pointers：両端から近づける」で何を学びますか？
左右のポインターを互いに近づけ、ソート済み配列の二数和、valid palindrome、trapping rain waterを解きます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「Two Pointers：両端から近づける」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 配列の基礎とin-place操作
- 累積和とランニングトータル
- Two Pointers：両端から近づける
- Two Pointers：遅いポインターと速いポインター