アルゴリズム概要

問題：整数配列 nums と整数 target が与えられたとき、和が target になる2要素の添字ペアを返す。

要件：

入出力例：

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
説明: nums[0] + nums[1] = 2 + 7 = 9

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

戦略：

ステップバイステップ解説

Python実装 

from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """
        ハッシュテーブル1パスでTwo Sumを解く

        Args:
            nums: 整数配列（長さ >= 2）
            target: 目標和

        Returns:
            和が target になる2要素の添字リスト [i, j]

        Time Complexity: O(n)
        Space Complexity: O(n)
        """
        seen: dict[int, int] = {}  # value -> first occurrence index

        for i, x in enumerate(nums):
            need = target - x

            # 補数が既出か確認
            if need in seen:
                return [seen[need], i]

            # 現在値を初出のみ登録（重複時は最左を保持）
            if x not in seen:
                seen[x] = i

        # 問題前提（解が必ず存在）により到達しないが型整合のため
        return [-1, -1]

フローチャート

開始 twoSum seen = {} を初期化 配列を走査 各 i, x について 要素あり need = target - x を計算 need が seen にあるか？ はい [seen[need], i] を返却 いいえ x が seen にあるか？ いいえ seen[x] = i を登録 はい スキップ 次の要素へ 配列終了 [-1, -1] を返却 終了

フローの説明：
1. 空の辞書 seen を初期化
2. 配列を左から順に走査（各要素を x、添字を i とする）
3. 補数 need = target - x を計算
4. need が辞書に存在するか確認 → 存在すれば即座に [seen[need], i] を返却
5. 存在しなければ、x が辞書に未登録なら seen[x] = i を登録
6. 次の要素へ進む（ループバック）
7. 全要素を処理しても解が見つからなければ終了（問題前提では到達しない）

計算量分析

指標 本実装（ハッシュ1パス） 二重ループ ソート+二ポインタ
時間計算量 O(n) O(n²) O(n log n)
空間計算量 O(n) O(1) O(n)
実装コスト 低 低 中
Follow-up対応 ✅ O(n²)未満 ❌ O(n²) ✅ O(n log n)

詳細分析：