Two Sum をハッシュマップで解く

配列とハッシュ問題 04

整数の並びから、足すと目標の数になる 2 つを探し、その位置を返す。見た数を辞書に覚えておくと、並びを 1 回なめるだけで見つかります。

海外で定番の問題リスト 4 本のうち 4 本に入っています (Blind 75、NeetCode 150、Grind 75、LeetCode Top Interview 150)

問題

整数の並び nums と、整数 target を受け取ります。nums の中から、足すと target になる 2 つの数を選び、その位置 (0 から数えた番号) を小さい順に並べて返す関数を書いてください。

答えになる組は、ちょうど 1 組だけあるものとします
同じ位置の数を 2 回使うことはできません。同じ値が別の位置に 2 つあれば、その 2 つは使えます
nums の長さは 2 以上 10000 以下、値はどれも絶対値が 10 億以下です

入力と出力の例

例 1

nums = [3, 8, 12, 5] target = 17

[2, 3]

例 2

同じ値でも、位置が違えば別の数として使えます。

nums = [6, 1, 6] target = 12

[0, 2]

例 3

負の数も入ります。

nums = [-4, 10, 7, 2] target = 3

[0, 2]

面接での聞かれ方

面接では、問題文がもっと短く渡されることが多いです。

「整数の配列と目標の数があります。足して目標になる 2 つの位置を返してください」
書き終えたあとに「いまの書き方の計算量は？」「もっと速くできますか？」と続けて聞かれます
「答えが無いときはどうしますか？」と、問題文に無い場合を聞かれることもあります

最初の一文だけで書き始めず、答えがいつも 1 組あるのか、同じ位置を 2 回使ってよいのかを、先に確かめてから書くと落ち着いて進められます。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「ハッシュマップ」に、この型の要点を表とコードでまとめています。

ハッシュは、値から番地を計算して、探す手間をほぼ 1 回にする仕組みです。重複や回数の問題は、この形で解けます。

まず考える手順

段 1

まずは素直に、2 つの組を全部試す書き方を考えます。1 つ目の位置 i と、それより後ろの位置 j を 2 重の繰り返しで回し、足して target になれば返します。これでも正しく動きます。

段 2

全部の組を試すと、長さが 10000 のとき、足し算は 5000 万回ほどになります。そこで、1 つ目の数を決めたら、相手は target から引いた数に決まることに目を向けます。「相手の数がもう出てきたか」をすぐに調べられれば、繰り返しは 1 重で済みます。

段 3

すぐに調べるには、辞書 (Python の dict、JavaScript の Map、Go の map) を使います。数を 1 つ見るたびに、まず相手が辞書にあるかを調べ、無ければ「この値はこの位置にあった」と辞書に書き足します。調べてから書き足す順にすると、同じ位置を 2 回使うことが起きません。

解答

Python

def pair_with_target(
    nums, target
):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            j = seen[need]
            return [j, i]
        seen[x] = i
    return []

JavaScript

function pairWithTarget(
  nums, target
) {
  const seen = new Map();
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    const x = nums[i];
    const need = target - x;
    if (seen.has(need)) {
      const j = seen.get(need);
      return [j, i];
    }
    seen.set(x, i);
  }
  return [];
}

Go

func pairWithTarget(
	nums []int, target int,
) []int {
	seen := map[int]int{}
	for i, x := range nums {
		need := target - x
		j, ok := seen[need]
		if ok {
			return []int{j, i}
		}
		seen[x] = i
	}
	return []int{}
}

答えは必ず 1 組あるので、最後の return [] に来ることはありません。面接で「無いときは？」と聞かれたら、空の並びを返すと決めてある、と答えられるように置いてあります。

計算量

時間は O(n) です。並びを前から 1 回なめ、辞書を調べるのも書き足すのも、平均して一定の手間で済みます
使う記憶は O(n) です。最悪の場合、ほぼ全部の数を辞書に覚えます
段 1 の 2 重の繰り返しは、時間が O(n²)、記憶は O(1) です。記憶を使う代わりに時間を縮めた、という取り引きになっています

よくある間違い

先に書き足してから調べる。 seen[x] = i を先に置くと、target がちょうど x の 2 倍のとき、自分自身を相手として見つけてしまいます。例 2 の [6, 1, 6] で 6 を 1 つしか使わずに答えたことになります
値で並べ替えてから探す。並べ替えると元の位置が分からなくなります。並べ替えるなら、位置を組にして持ち歩く必要があります
返す順を気にしない。辞書から取り出した位置は、いま見ている位置より必ず前なので、[seen[need], i] の順に返せば小さい順になります

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.2確認日 2026年10月24日

def pair_with_target(nums: list[int], target: int) -> list[int]: """ Goal: 何を返すか idea1: まず思いつく案 -> runtime: O(?) space: O(?) idea2: もっと速い案 -> runtime: O(?) space: O(?) edge case: 空、1 つだけ、など """ # ここに書きます pass # 「実行」を押すと、この行の結果が出ます print(pair_with_target([3, 8, 12, 5], 17))