Two Sum
整数の配列 nums と整数 target が与えられます。nums のちょうど2つの要素が異なる位置にあり、その合計は target になります。その2つの要素のインデックスを、小さい方を先にして返してください。
関数
- numsinteger-array
- 検索する整数の配列
- targetinteger
- 2つの項目の合計が達しなければならない値
- 戻り値integer-array
- 2つのインデックス。小さい方が先
制約
2 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109-109 ≤ target ≤ 109- 異なる位置のペアで、合計が
targetになるものはちょうど1組です。
例
- 入力
- nums = [3, 8, 12, 5]target = 17
- 出力
- [2, 3]
- 説明
- 12 はインデックス 2 にあり、5 はインデックス 3 にあります。また、12 + 5 = 17 です。ほかに 17 になるペアはありません。
- 入力
- nums = [6, 1, 4, 10]target = 7
- 出力
- [0, 1]
- 説明
- インデックス 0 の 6 とインデックス 1 の 1 を足すと 7 になります。このペアは最初の 2 つの要素にできます。
- 入力
- nums = [2, -6, 9, 4, 13]target = 3
- 出力
- [1, 2]
- 説明
- インデックス 1 の -6 とインデックス 2 の 9 を足すと 3 になります。負の数も正の数と同じように組み合わせます。
発展問題
numsがすでにソートされていたら、追加メモリをO(1)だけ使って、O(n)時間でペアを見つけられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
二重ループですべてのペアを試す方法は正しいですが、10,000個の数値では約5,000万回のチェックが必要です。リストをもう一度走査せずに、それぞれの数値の組み合わせ相手を見つけられますか？
値
xに注目すると、ペアを完成させる値が何かはすでにわかっています。目標値からxを引いた値です。問題は、その値を以前に通過したかどうか、そしてそのインデックスがどこかだけです。リストを一度走査し、通過した各値とそのインデックスをハッシュマップに保持します。各位置で、足りない相手の値をまず検索します。マップにあれば、2つのインデックスが見つかったことになります。そうでなければ、現在の値を保存して次に進みます。保存する前に検索することで、数値が自分自身と組になるのを防げます。
解説
すべてのペアを調べる方法でも動作しますが、処理量は長さの二乗に応じて増えます。問いを逆に考えてみましょう。数値 x に注目すると、その相方は target - x であるとすでにわかっています。ハッシュマップを使えば、その値をすでに通過したかどうかを定数時間で確認できるため、1回の走査で十分です。
すべてのペアを確認する
正しいが、最大のテストでは終わらない
考え方
最初のインデックス i を固定し、右側にある各インデックス j を試して、nums[i] + nums[j] が target と等しくなるまで調べます。j を i + 1 から始めることで、同じ位置同士の組み合わせを避け、各ペアを一度ずつ試し、小さい方のインデックスを先にできます。探しているペアは試すペアの中にあるので、見つけられます。
n 個の数は約 n²/2 個のペアを作ります。n = 10^4 の場合、加算の回数は約 5 × 10^7 回になります。
アルゴリズム
numsのすべてのインデックスについて、iをループします。- 各
iについて、i + 1から最後のインデックスまでjをループします。 nums[i] + nums[j]がtargetと等しければ、[i, j]を返します。- 両方のループが終了した場合は、空の配列を返します。問題の条件上、このようなことは起こりません。
def twoSum(nums, target):
n = len(nums)
for i in range(n):
# Only look at partners to the right, so each pair is checked once.
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []ハッシュマップを使った1回の走査
考え方
固定された nums[i] に対して、力任せの内側のループは、あらかじめ分かっている1つの値、target - nums[i] を探します。この走査は実質的には検索であり、値からインデックスへのハッシュマップを使えば、平均して定数時間で検索できます。
まず検索し、その後に格納します。そうすれば、数値はそれより前にある値としか組み合わせられず、自分自身とは組み合わせられません。また、相手は必ず前にあるため、そのインデックスが先になります。各数値を1回だけ確認し、定数時間のマップ操作を行うので、探索は O(n) です。その代わり、最大で n 件のエントリーを持つマップが必要です。
アルゴリズム
- 値からインデックスへの空のマップを作成します。
- 各インデックス
iについて、ペアを完成させる値であるneedを計算します。つまり、targetからnums[i]を引いた値です。 needがマップにある場合は、保存されているインデックスの後にiを続けて返します。- それ以外の場合は、
nums[i]をインデックスiとともに保存して続けます。
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
need = target - num
if need in seen:
return [seen[need], i]
seen[num] = i
return []
落とし穴と境界ケース
- 相手を探す前に数値を保存すること。
[4, 2, 6]とtarget = 8の場合、4 は自分自身を見つけ、[0, 0]を返します。 - インデックスを誤った順序で返すこと。検索してから保存すれば、マップ内のインデックスのほうが小さいため、先に置きます。
- 2つのポインターを使うために配列をソートし、ソート後のコピー内での位置を返すこと。各値の元のインデックスを隣に保持してください。
- 値が正または重複しないと決めつけること。
[0, 7, -3, 0]とtarget = 0の場合、2つのゼロが組になります。[0, 3]。 - Lua と R で、1始まりのインデックスを返すこと。それぞれから 1 を引いてください。
よくある質問3
Two Sum の時間計算量はどれくらいですか？
ハッシュマップを使った解法は、各数値を1回ずつ調べ、各検索や挿入が平均して定数時間で済むため、時間計算量は O(n) です。マップ用に追加で O(n) の空間を使います。すべてのペアを調べる場合、時間計算量は O(n²)、空間計算量は O(1) です。
Two Sumは追加の領域を使わずに解けますか？
ソートされていない配列では、線形時間では実行できません。追加の領域が O(1) だと、すべてのペアを再び確認することになり、これは O(n²) です。ハッシュマップは O(n) のメモリと引き換えに、線形時間を実現します。
Two Sum では重複する数値をどのように処理しますか？
現在の数値を保存する前に相手を検索すれば、重複する値にも対応できます。target = 14の[7, 3, 7]では、最初の7がインデックス0に保存され、2つ目の7がそれを見つけるため、[0, 2]が得られます。7が1つだけの場合、自分自身とは組になりません。検索する時点では、まだマップに登録されていないからです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def twoSum(nums, target):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [3, 8, 12, 5] target = 17
期待される出力
[2, 3]