Two Sum
整数のリストと目標値が与えられます。リスト内のちょうど2つの数を足すと目標値になるので、それらがどこにあるかを報告してください。
nums = [3, 8, 12, 5]、target = 17 とします。値 12 はインデックス2にあり、5 はインデックス3にあります。12 + 5 = 17 なので、答えは [2, 3] です。
2つの数は、異なる位置から選ばなければなりません。[4, 2, 6] で target = 8 の場合、4を2回使うことはできません。2 + 6 = 8 なので、答えは [1, 2] です。ただし、同じ値が2回現れてもかまいません。[7, 3, 7] で target = 14 の場合、答えは [0, 2] です。
整数の配列 nums と整数 target を受け取り、nums[i] + nums[j] が target と等しくなるような2つのインデックス [i, j] の配列を返す、twoSum という名前の関数を書いてください。
インデックスは異なる位置を指し、昇順(i が j より小さい順)で返す必要があります。すべての入力には、そのようなペアがちょうど1つ存在します。
制約:2 ≤ nums.length ≤ 10^4、-10^9 ≤ nums[i] ≤ 10^9、-10^9 ≤ target ≤ 10^9。
関数
- arg1integer-array
- arg2integer
- 戻り値integer-array
例
- 入力
- arg1 = [3, 8, 12, 5]arg2 = 17
- 出力
- [2, 3]
- 入力
- arg1 = [6, 1, 4, 10]arg2 = 7
- 出力
- [0, 1]
- 入力
- arg1 = [2, -6, 9, 4, 13]arg2 = 3
- 出力
- [1, 2]
提出時に隠しテスト+13件
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
二重ループですべてのペアを試す方法は正しいですが、10,000 個の数値では約 5,000 万回のチェックが必要です。リストをもう一度走査せずに、それぞれの数値と組になる数値を見つけられますか?
値
xに注目すると、ペアを完成させる値が何かはすでにわかっています。つまり、target からxを引いた値です。あとは、その値をすでに通過したかどうか、またそのインデックスがどれかだけが問題です。リストを1回走査し、通過した各値とそのインデックスをハッシュマップに保持します。各位置で、まず不足している相方を検索します。それがマップにあれば、両方のインデックスが見つかったことになります。そうでなければ、現在の値を保存して次に進みます。保存する前に検索することで、数値が自分自身と組になるのを防げます。
この問題の詳しい解説は準備中です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def twoSum(nums, target):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
arg1 = [3, 8, 12, 5] arg2 = 17
期待値
[2, 3]