Two-Sumとその多様な派生問題
ハッシュマップとTwo Pointersを使い、two-sum、three-sum、four-sum、ソート済み配列のtwo-sumを解き、時間と空間のコストを比較します。
「Two-Sumとその多様な派生問題」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
Two-Sum：面接の定番問題
LeetCode 1 の「Two Sum」では、ソートされていない配列と target が与えられたとき、合計が target になる2つの要素のインデックスを返します。O(n²) の総当たり法では、すべてのペアを調べます。最適な O(n) の方法ではハッシュマップを使い、各要素 x について、target - x がすでにマップに存在するかを確認します。存在すれば、その2つのインデックスのペアを返します。存在しなければ、x とそのインデックスをマップに保存します。
two-sum は面接で最初に出される問題であることが多く、これを確実に解けると、より難しい問題に進む準備ができていることを示せます。
def twoSum(nums, target):
seen = {} # val -> index
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return [seen[complement], i]
seen[x] = i
return []
print(twoSum([2, 7, 11, 15], 9)) # [0, 1]
print(twoSum([3, 2, 4], 6)) # [1, 2]
print(twoSum([3, 3], 6)) # [0, 1]Two-Sum でハッシュマップが機能する理由
ハッシュマップには、それまでに確認したすべての要素を保存します。要素 x を処理するとき、target - x がマップにあれば、その2つの要素は有効なペアになります。重要なのは、x を保存する前に必ず補数を確認することです。これにより、1つの要素自身とペアにしてしまうケースを防げます（たとえば x == target/2 の場合、x を保存する前にマップを確認するため、同じ値が2つ存在しない限り一致しません）。
# Trace two-sum on [2, 7, 11, 15], target=9
nums, target = [2, 7, 11, 15], 9
seen = {}
for i, x in enumerate(nums):
complement = target - x
print(f'i={i} x={x} complement={complement} seen={seen}')
if complement in seen:
print(f' Found: indices [{seen[complement]}, {i}]')
break
seen[x] = iソート済み配列の Two-Sum（2ポインター）
配列がすでにソート済みで、元のインデックスではなく値のインデックスが必要な場合は、2ポインター法を使います。これは、左右の端から始める left と right のポインターを使う方法です。合計が target と等しければ、その結果を返します。合計が小さすぎれば left を右に動かし、大きすぎれば right を左に動かします。計算量は時間 O(n)、空間 O(1) です。配列がソート済みでメモリに制約がある場合、ハッシュマップを使う方法より優れています。
def twoSumSorted(numbers, target):
lo, hi = 0, len(numbers) - 1
while lo < hi:
s = numbers[lo] + numbers[hi]
if s == target:
return [lo + 1, hi + 1] # 1-indexed as per LeetCode 167
elif s < target:
lo += 1
else:
hi -= 1
return []
print(twoSumSorted([2, 7, 11, 15], 9)) # [1, 2]
print(twoSumSorted([2, 3, 4], 6)) # [1, 3]
print(twoSumSorted([-1, 0], -1)) # [1, 2]Three-Sum（LeetCode 15）
LeetCode 15 の「Three Sum」では、合計が0になる重複のない3要素の組をすべて見つけます。配列をソートし、1つの要素を順に固定して、残りのソート済み部分配列に2ポインター法を適用します。重複する値をスキップして、同じ組が重複しないようにします。計算量は O(n²) です。出力自体に O(n²) 個の組が含まれる可能性があるため、この問題では最適な計算量です。
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: # skip duplicates
continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < 0:
lo += 1
else:
hi -= 1
return result
print(threeSum([-1, 0, 1, 2, -1, -4])) # [[-1,-1,2],[-1,0,1]]
print(threeSum([0, 0, 0, 0])) # [[0,0,0]]Four-Sum（LeetCode 18）
LeetCode 18 の「Four Sum」では、合計が target になる重複のない4要素の組をすべて見つけます。Three-Sum を拡張し、2つの要素を2重ループで固定して（重複をスキップします）、その内側の部分配列に2ポインター法を適用します。計算量は O(n³) です。一般的な k-sum では、k-2 回再帰してから2ポインター法を適用するパターンになり、計算量は O(n^(k-1)) です。
def fourSum(nums, target):
nums.sort()
n, result = len(nums), []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]:
continue
lo, hi = j+1, n-1
while lo < hi:
s = nums[i]+nums[j]+nums[lo]+nums[hi]
if s == target:
result.append([nums[i],nums[j],nums[lo],nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target: lo += 1
else: hi -= 1
return result
print(fourSum([1,0,-1,0,-2,2], 0))
# [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]target に最も近い Two-Sum
よくある応用問題として、合計が target と完全には一致しなくても、target に最も近い合計になるペアを見つける問題があります。配列をソートして2ポインター法を使います。これまでに見つけた最も近い合計を記録し、target との差の絶対値がより小さいペアを見つけるたびに更新します。ソート後の計算量は O(n) なので、全体では O(n log n) となり、わかりやすい方法です。
def twoSumClosest(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
best = float('inf')
best_pair = None
while lo < hi:
s = nums[lo] + nums[hi]
if abs(s - target) < abs(best - target):
best = s
best_pair = (nums[lo], nums[hi])
if s < target:
lo += 1
elif s > target:
hi -= 1
else:
return best_pair # exact match
return best_pair
print(twoSumClosest([1, 3, 4, 7, 10], 15)) # (7, 10) => 17, closest to 15
print(twoSumClosest([2, 5, 8, 11], 10)) # (2, 8) => 10, exact!複数のペアを持つ Two-Sum（すべてのペア）
合計が target になるすべてのペアを見つけるには、配列をソートして2ポインター法を使い、すべてのペアを収集します。有効なペアを見つけたら、続行する前に両端から重複をスキップします。これにより、ソートに O(n log n)、走査に O(n) かかるため、全体の計算量は O(n log n) です。ペアの収集にハッシュマップを使う方法も有効ですが、重複を慎重に扱う必要があります。
def twoSumAllPairs(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
pairs = []
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
pairs.append((nums[lo], nums[hi]))
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target:
lo += 1
else:
hi -= 1
return pairs
print(twoSumAllPairs([1,1,2,3,4,4,5], 5)) # [(1,4),(1,4)-deduped,(2,3)]
# After duplicate-skipping: [(1,4),(2,3)]合計が K 未満になるペアの数え上げ
別の応用として、合計が k 未満になるペアの数を数える問題があります。配列をソートし、2ポインター法を使います。nums[lo] + nums[hi] < k の場合、(lo, lo+1)、(lo, lo+2)、…、(lo, hi) のすべてのペアが条件を満たします。つまり、ペアは hi - lo 個あります。lo を進めます。それ以外の場合は hi を縮めます。計算量は、ソートに O(n log n)、数え上げに O(n) かかります。
def countPairsLessThan(nums, k):
nums.sort()
lo, hi = 0, len(nums) - 1
count = 0
while lo < hi:
if nums[lo] + nums[hi] < k:
count += hi - lo # all (lo, lo+1)...(lo, hi) are valid
lo += 1
else:
hi -= 1
return count
print(countPairsLessThan([1, 3, 7, 11, 12], 10)) # (1,3),(1,7),(3,7) => 3
print(countPairsLessThan([3, 5, 2, 3], 7)) # (2,3),(2,3) => 2... verifyハッシュマップを使った Two-Sum：重複の扱い
同じ値が複数回現れる可能性があり、有効なペアの存在だけでなく個数が必要な場合は、マップに出現頻度を保存します。2つの要素が等しいペアでは、出現頻度 f から作れるペアの数は f*(f-1)//2 です。2つの要素が異なる場合は、それぞれの出現頻度を掛け合わせます。これにより、すべての有効なペアを O(n) で数えられます。
from collections import Counter
def countTwoSumPairs(nums, target):
freq = Counter(nums)
count = 0
seen = set()
for x in freq:
y = target - x
if y in freq and (x, y) not in seen:
if x == y:
count += freq[x] * (freq[x] - 1) // 2
else:
count += freq[x] * freq[y]
seen.add((x, y))
seen.add((y, x))
return count
print(countTwoSumPairs([1,1,2,3,4,4,3], 4))
# Pairs summing to 4: (1,3)x2x2=4, (0+more)...Two-Sum のパターンの応用を見抜く
two-sum のパターンは、さまざまな形で登場します。数値的な関係（和、積、差など）を満たす2つ以上の要素を見つける問題が出たら、このパターンを見抜いてください。基本戦略は常に同じです。1つの要素を固定し、事前に用意したデータ構造（ハッシュマップ、またはソート済み配列とポインターの組み合わせ）からその補数を探します。k-sum へは、k-2 個の要素を入れ子のループで固定し、基本ケースを適用することで拡張できます。
# Summary of approaches by scenario
scenarios = [
('Unsorted array, any indices, one pair', 'hash map O(n) time O(n) space'),
('Sorted array, any indices, one pair', 'two pointers O(n) time O(1) space'),
('All unique pairs summing to target', 'sort + two pointers O(n log n)'),
('Three numbers summing to zero (3-sum)', 'sort + fix + two pointers O(n^2)'),
('k numbers summing to target (k-sum)', 'sort + k-2 loops + two pointers O(n^(k-1))')
]
for scenario, approach in scenarios:
print(f'{scenario}\n => {approach}\n')Two-Sum での面接中の伝え方
面接で two-sum が出たら、考えていることを声に出して説明してください。「target になる2つの数が必要です。各数 x について、target-x が存在するか確認する必要があります。ハッシュマップを使えばこれを O(1) で判定できるので、全体の時間計算量は O(n)、空間計算量は O(n) です。別の方法として、配列がソート済みなら2ポインター法を使い、空間計算量を O(1) にできます」。両方の方法を示し、選択する前に空間計算量の制約があるか尋ねてください。
理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、two-sum はハッシュマップを使って補数の存在を O(1) で確認するため、全体の計算量は O(n) になること、ソート済み配列では two pointers によって空間計算量を O(1) にできること、そしてthree-sum と four-sum はソートとネストしたループによって two-sum に帰着でき、それぞれ O(n²) と O(n³) で実行できることを学びました。次は、頻度カウントのパターンと defaultdict、Counter を使ったグループ化について学びます。
よくある質問
「Two-Sumとその多様な派生問題」レッスンは無料ですか？
はい。「Two-Sumとその多様な派生問題」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「Two-Sumとその多様な派生問題」で何を学びますか？
ハッシュマップとTwo Pointersを使い、two-sum、three-sum、four-sum、ソート済み配列のtwo-sumを解き、時間と空間のコストを比較します。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「Two-Sumとその多様な派生問題」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- ハッシュ関数の内部動作と衝突処理
- Two-Sumとその多様な派生問題
- 頻度カウントとグループ化
- 最長連続列とLRUキャッシュ