PROBLEM 01
2つの数で目標を作る
配列を1回走査し、目標値を作る2要素の位置を返します。
あるイベントの会計記録に、1件ずつ金額が並んでいます。 異なる2件を選び、その合計が指定された目標額になる組を見つけてください。
twoSum(nums, target) は、条件を満たす2要素の位置を配列 [i, j] で返します。
答えは必ず1組だけ存在し、同じ位置を2回使うことはできません。
例
入力: nums = [4, 13, 7, 2], target = 9
出力: [2, 3]
理由: nums[2] + nums[3] = 7 + 2 = 9入力: nums = [5, 1, 5, 8], target = 10
出力: [0, 2]制約
2 <= nums.length <= 50,000- 各値と
targetは安全な整数の範囲内 - 条件を満たす組はちょうど1つ
対応する問題: LeetCode #1 Two Sum
STEPWISE HINTS
ヒント
01考え方の方向
今見ている値と組み合わせて target になる値を、過去に見たかどうか考えます。
02使うデータ構造
値をキー、配列の位置を値にした Map を用意すると、相方を定数時間で探せます。
03擬似コード
各 nums[i] について target - nums[i] を Map で探す。見つかれば位置を返し、なければ nums[i] と i を保存する。
AFTER ACCEPTED
解説
AC 後に解説が開きます
まずは自分の言葉で方針を説明し、コードに落としてみましょう。