Guppi StudioPROBLEM 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]
理由: 同じ「値」は使えるが、同じ「位置」は使えない。nums[0] + nums[2] = 5 + 5 = 10制約
2 <= nums.length <= 50,000- 各値と
targetは安全な整数の範囲内 - 条件を満たす組はちょうど1つ
- 目標: O(n) 相当（二重ループ解は性能テストで時間切れになります）
対応する問題: LeetCode #1 Two Sum
まず素朴に解くと — 全ペアを試す
最初に思いつくのは「2つ選ぶ組み合わせを全部試す」二重ループです。まずこれが書ければ正解には到達できます。
function twoSum(nums: number[], target: number): number[] {
for (let i = 0; i < nums.length; i += 1) {
for (let j = i + 1; j < nums.length; j += 1) {
if (nums[i] + nums[j] === target) return [i, j];
}
}
return [];
}ペアの数は n × (n - 1) / 2 なので、時間計算量は O(n²) です。
どこが遅いのか
この問題の性能テストは 50,000 要素で、答えの組は配列の末尾付近にあります。O(n²) 解はおよそ 12.5億ペア を調べることになり、模範解答（数ミリ秒）の12倍という制限時間に収まりません。
遅さの正体は、nums[i] を手に取るたびに残り全部を探し直していることです。
発想の転換
探し回るのをやめて、「今までに見た値」を覚えておく。
nums[i] を見た瞬間、必要な相方は target - nums[i] だと確定します。つまり知りたいのは「その値を過去に見たか、見たなら何番目か」だけ。これは「値 → 位置」の Map があれば O(1) で答えられます。配列は1周で済みます。
解答例 — O(n)
function twoSum(nums: number[], target: number): number[] {
const seen = new Map<number, number>();
for (let i = 0; i < nums.length; i += 1) {
const pair = seen.get(target - nums[i]);
if (pair !== undefined) return [pair, i];
seen.set(nums[i], i);
}
return [];
}ポイントは**「相方を探してから、自分を登録する」順序**です。先に登録すると target = 8, nums[i] = 4 のような場面で自分自身（同じ位置）を相方にしてしまいます。この順序なら Map にあるのは常に「過去の値」だけなので、同じ位置の二重使用が起きません。
動きを追う — nums = [4, 13, 7, 2], target = 9
| i | nums[i] | 探す相方 | Map にある？ | 処理後の Map（値→位置） |
|---|---|---|---|---|
| 0 | 4 | 5 | ない | 4→0 |
| 1 | 13 | -4 | ない | 4→0, 13→1 |
| 2 | 7 | 2 | ない | 4→0, 13→1, 7→2 |
| 3 | 2 | 7 | ある（位置2） | → [2, 3] を返す |
計算量の比較
| 解法 | 時間 | 追加領域 | n = 50,000 での操作回数の目安 |
|---|---|---|---|
| 二重ループ | O(n²) | O(1) | 約12.5億 |
| Map で1周 | O(n) | O(n) | 約5万 |
面接でどう話すか
「全ペアを試す O(n²) がまず考えられますが、n が5万なので10億回規模になり遅すぎます。各要素で必要な相方は
target - nums[i]と一意に決まるので、見た値を『値→添字』の Map に記録しながら1周すれば O(n) です。相方を探してから登録する順にして、同じ要素の二重使用を防ぎます。」
このように素朴解に触れてから改善する流れで話すと、計算量を見積もってから設計している姿勢が伝わります。書き始める前に方針と計算量を面接官へ確認するのが定石です。
STEPWISE HINTS
ヒント
01最初の一手
今見ている値と組み合わせて target になる値を、過去に見たかどうか考えます。
02処理の組み立て
値をキー、配列の位置を値にした Map を用意すると、相方を定数時間で探せます。
03コードの形
各 nums[i] について target - nums[i] を Map で探す。見つかれば位置を返し、なければ nums[i] と i を保存する。
AFTER ACCEPTED
解説
まずは自分の言葉で方針を説明し、コードに落としてみましょう。