Pythonで解く「Two Sum（2つの合計）」問題：ハッシュマップを使った効率的な実装方法

整数の配列が与えられたとき、その中から2つの要素を選び、その合計が指定されたターゲット値と一致するようなインデックスのペアを返す問題を考えてみましょう。これは、アルゴリズム学習やコーディング面接で非常によく知られている「Two Sum（2つの合計）」問題です。

ここでは、配列内に必ず一意な解が1つだけ存在するという前提を置きます。つまり、同じターゲットに対して複数のインデックスの組み合わせが存在することはありません。

問題の例

例として、配列 A = [2, 8, 12, 15]、ターゲットの合計値が 20 である場合を考えます。このとき A[1] + A[2] = 8 + 12 = 20 となるため、答えはインデックス 1 と 2 を返します。

解法のアプローチ：ハッシュマップ（辞書）を活用

最も単純な方法は全てのペアを総当たりで調べることですが、計算量が O(n²) となり非効率です。そこで、ハッシュマップ（Pythonでは辞書）を使うことで、時間計算量 O(n) で解くことができます。

基本的な考え方は次の通りです。配列を先頭から順に走査しながら、「現在の要素と足し合わせてターゲットになる値（補数）」がすでに登場済みかどうかを辞書で確認します。

具体的な手順

• 結果を保持するための空の辞書（マップ）res を用意する
• インデックス i を 0 から n - 1 まで順にループする（n は配列の要素数）
  • もし target - A[i]（補数）がすでに res に存在すれば、その補数のインデックスと現在の i を答えとして返す
  • 存在しなければ、res[A[i]] = i として現在の値とインデックスを記録する

この方法なら、各要素を一度ずつ調べるだけで済むため、非常に効率的です。

Pythonでの実装例

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        required = {}
        for i in range(len(nums)):
            if target - nums[i] in required:
                return [required[target - nums[i]], i]
            else:
                required[nums[i]] = i

input_list = [2, 8, 12, 15]
ob1 = Solution()
print(ob1.twoSum(input_list, 20))

入力

input_list = [2, 8, 12, 15]
target = 20

出力

[1, 2]

まとめ

この実装では、辞書 required に「これまでに見た値 → インデックス」を記録していきます。各要素について、ターゲットとの差分（補数）がすでに記録済みかどうかを O(1) で確認できるため、全体の処理は線形時間で完了します。

空間計算量は O(n)、時間計算量は O(n) となり、総当たり方式（O(n²)）と比べて大幅に効率化できるのがポイントです。「Two Sum」はハッシュマップ活用の基本形となる問題なので、ぜひこのパターンを覚えておきましょう。