Two Sum II: Sorted Input
整数配列 numbers が非減少順にソートされた状態で与えられ、整数 target が与えられます。異なる位置にある2つの値の合計が target になる組はちょうど1つです。その2つの位置を0始まりのインデックスで返してください。インデックスの小さい方を先にしてください。
関数
- numbersinteger-array
- 整数のソート済み配列
- targetinteger
- 2つの値の合計が達しなければならない値
- 戻り値integer-array
- i < j かつ numbers[i] + numbers[j] == target を満たす、0始まりの2つのインデックス [i, j]
制約
2 ≤ numbers.length ≤ 104-5 × 108 ≤ numbers[i] ≤ 5 × 108-109 ≤ target ≤ 109numbersは非減少順に並んでいます。- インデックスの組
i < jはちょうど1つだけ存在し、numbers[i] + numbers[j] == targetを満たします。
例
- 入力
- numbers = [-4, 1, 3, 8, 12]target = 9
- 出力
- [1, 3]
- 説明
- 1 はインデックス 1 にあり、8 はインデックス 3 にあります。また、1 + 8 = 9 です。ほかに 9 になるペアはありません。たとえば、-4 + 12 = 8 です。
- 入力
- numbers = [2, 2, 5, 7]target = 4
- 出力
- [0, 1]
- 説明
- インデックス0と1にある2つは異なる位置にあるため、ペアを形成できます：2 + 2 = 4。
- 入力
- numbers = [-10, -3, 0, 6]target = -4
- 出力
- [0, 3]
- 説明
- インデックス0の-10とインデックス3の6を足すと、-10 + 6 = -4になります。答えは配列全体にわたることがあります。
提出時に隠しテスト+13件
発展問題
追加メモリ O(1) で、O(n) 時間で解けますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
配列はソートされています。最小値と最大値を一緒に見てみましょう。それらの合計が
targetより小さいとき、何がわかりますか？最初の値と最後の値の合計が小さすぎる場合、最後の値はすでに最大なので、最初の値はどの相手と組み合わせても小さすぎます。最初の値を候補から外せます。
両端にそれぞれポインターを置きます。合計が小さすぎる場合は左のポインターを右へ動かし、大きすぎる場合は右のポインターを左へ動かします。合計が
targetと等しくなったら停止します。
解説
ハッシュマップを使えば、ソートされていない場合の問題は1回の走査で解けますが、O(n)のメモリが必要です。ここでは配列がソートされているので、その順序を手がかりに移動する方向を決められます。両端にポインターを1つずつ置きます。合計が小さすぎる場合は、左側の値を大きくすることでしか改善できません。大きすぎる場合は、右側の値を小さくすることでしか改善できません。各ステップで値を1つ確実に候補から除外できるため、追加のメモリを使わずに1回の走査でペアを見つけられます。
すべてのペアを確認する
正しいが、最大のテストでは終わらない
考え方
位置のすべての組み合わせ i < j を試し、numbers[i] + numbers[j] が target と等しいかを確認します。i は左から順に進み、j はそのすぐ後から始まるため、最初に見つかる組み合わせでは、すでに小さいインデックスが先になっています。
これは正しい方法ですが、ソート済みであることを活用していません。n = 10^4 の場合、組み合わせは約 5 × 10^7 個あり、答えが配列の末尾近くにあると、そのほぼすべてを調べることになります。大規模なテストには遅すぎます。
アルゴリズム
- すべてのインデックスについて
iをループします。 i+1から最後のインデックスまでjをループします。numbers[i] + numbers[j]がtargetと等しい場合、[i, j]を返します。
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n):
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
return [i, j]
return []各ペアに対する二分探索
考え方
最初の値 numbers[i] を決めると、その相手は正確に target - numbers[i] だとわかります。配列の i より右の部分はソートされているので、二分探索を使えば、その相手があるかどうかを O(log n) ステップで判定できます。
[-4, 1, 3, 8, 12] と target = 9 の場合、i = 0 では相手は13ですが、見つかりません。i = 1 では相手は8で、探索するとインデックス3で見つかります。答えは [1, 3] です。
i より右だけを探索することで、小さい方のインデックスが先になり、値がそれ自身と組み合わされるのを防げます。ペアは一意なので、その範囲内に相手の値が現れるのは最大1回であり、一致する値があればそれが答えです。合計で、O(log n) の探索を n 回行います。
アルゴリズム
iを 0 からn-2までループします。need = target - numbers[i]を計算します。- インデックス
i+1からn-1の範囲でneedを二分探索します。 midで見つかった場合は、[i, mid]を返します。
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n - 1):
need = target - numbers[i]
lo, hi = i + 1, n - 1
while lo <= hi:
mid = (lo + hi) // 2
if numbers[mid] == need:
return [i, mid]
if numbers[mid] < need:
lo = mid + 1
else:
hi = mid - 1
return []両端からの2つのポインター
考え方
left = 0 と right = n-1 から始め、numbers[left] + numbers[right] を確認します。これが target と等しければ完了です。小さすぎる場合、numbers[left] は答えの一部にはなり得ません。残っている最大の値と組み合わせても、目標に届かないからです。そこで left を右に移動します。合計が大きすぎる場合も、numbers[right] は答えの一部にはなり得ません。残っている最小の値と組み合わせても、目標を超えてしまうからです。そこで right を左に移動します。
移動するたびに、ペアに含まれる可能性がない値を1つ除外しますが、ペアそのものが除外されることはありません。ポインターは最大でも n-1 回の移動でぶつかるため、走査は O(n) で、使用する変数は2つです。
target = 9 のときの [-4, 1, 3, 8, 12] では、-4 + 12 = 8 は小さすぎるため、left をインデックス1に移動します。次に、1 + 12 = 13 は大きすぎるため、right をインデックス3に移動します。これで 1 + 8 = 9 となり、答えは [1, 3] です。
アルゴリズム
leftを0に、rightをn-1に設定します。left < rightである間、total = numbers[left] + numbers[right]を計算します。totalがtargetと等しい場合、[left, right]を返します。totalが小さい場合はleftに1を加え、大きい場合はrightから1を引きます。
def twoSumSorted(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left, right]
if total < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
return []
落とし穴と境界ケース
ツーポインタ法のループは短いため、バグはその周辺の細部に潜んでいます。
- 位置を1始まりで返す。このバージョンではインデックスは0始まりです。
[-4, 1, 3, 8, 12]とtarget = 9の場合、答えは[2, 4]ではなく[1, 3]です。LuaとRでは、返す前に1を引いてください。 left <= rightでループする。ポインタが一致すると、同じ値を2回使って合計を計算することになります。- 間違ったポインタを動かす。合計が小さすぎる場合は、より大きな値が必要です。それを与えられるのは
leftだけです。 - 重複する値を拒否する。
target = 4のとき、[2, 2, 5, 7]では、異なる位置にある2つの2を使います。 - オーバーフロー。この問題の制約では、すべての合計が32ビット整数の範囲内に収まります。値が
10^9に達する可能性がある場合は、64ビット型で加算してください。
よくある質問4
ソート済み配列で Two Sum を解くとき、なぜ2つのポインターが有効なのでしょうか？
Two Sum II の時間計算量は何ですか？
2ポインター解法は、時間計算量が O(n)、追加の空間計算量が O(1) です。各ステップでポインターを1つ内側に移動し、最大でも n-1 ステップでポインター同士が出会います。各相手を二分探索すると O(n log n) かかり、すべてのペアを調べると O(n²) かかります。
最初の Two Sum のようにハッシュマップを使わないのはなぜですか？
ハッシュマップでも解け、実行時間は O(n) ですが、最大で n 個の値を格納します。ソート済みであるため、そのメモリは不要です。2つのポインターは合計値だけでどちらに動かせばよいか判断できます。面接官がこのバージョンを尋ねるのは、与えられた順序を活用できるかを見るためです。
ここでは、二分探索はどのような場合に適していますか？
一方の値が固定されていて、もう一方の値だけが必要な場合です。numbers[0]がペアに含まれる必要があるなら、1回の二分探索でO(log n)で相手のインデックスが見つかります。未知のペアを見つけるには、2つのポインターによる走査のほうが、n回の個別の探索より高速です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def twoSumSorted(numbers, target):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
numbers = [-4, 1, 3, 8, 12] target = 9
期待値
[1, 3]