Two Sum - LeetCode 1

外資系IT企業(Google, Amazon, Microsoft, Indeedなど)で、必ず行われる技術面接の1つであるコーディング試験対策として最も有名なLeetCodeというサイトの問題の中で、一番有名なTwo Sumという問題を解説します。

🎥 解説動画

🔍 アプローチ

すべてのペアを確認すると、2重ループが必要なので計算量は $$O(n^2)$$ nはインプットの長さになります。

入力: nums = [2,7,11,15], target = 9

すべてのペアを列挙すると：

[2,2] [2,7] [2,11] [2,15]
[7,2] [7,7] [7,11] [7,15]
[11,2] [11,7] [11,11] [11,15]
[15,2] [15,7] [15,11] [15,15]
→ 計16通り（4×4）

長さ4でも16回、長さ100なら1万回、1000なら100万回のループになります。

✅ 改善方法

O(n) にすれば、100個なら100回、1000個なら1000回で済みます！

この改善には「記憶（メモリ）を使う」ことがポイントです。

🧠 ポイント

探索済みの情報を HashMap に保存しておくことで、探索を高速化します。

🎯 例題に戻って考える

入力: nums = [2,7,11,15], target = 9

現在の数から目標値を引いた値が、すでに発見した数字ならペアが見つかったということになります。

9 - 2 = 7

つまり、今「2」なら「7」があればOK！

この「必要な値（= target - num）」が HashMap にあるかどうかを調べるのがキーです。

🔑 HashMapに保存すべき内容

• 数字（要素）をキーに
• そのインデックスを値として保持

🔁 Step by Step

入力: nums = [2,7,11,15], target = 9

初期状態：

pair_idx = {}

1. 2 → 必要なのは 7 → まだ pair_idx にない → 保存

pair_idx = {2: 0}

1. 7 → 必要なのは 2 → ある！ → 解答は [0,1]（または [1,0]）

その後も続けてみると：

1. 11 → 9 - 11 = -2 → なし → 保存

pair_idx = {2: 0, 7: 1, 11: 2}

1. 15 → 9 - 15 = -6 → なし → 保存

pair_idx = {2: 0, 7: 1, 11: 2, 15: 3}

🧑‍💻 解法コード

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        pair_idx = {}
        for i, num in enumerate(nums):
            if target - num in pair_idx:
                return [i, pair_idx[target - num]]
            pair_idx[num] = i

JavaScript

var twoSum = function(nums, target) {
    const pairIdx = {};
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        if (target - num in pairIdx) {
            return [i, pairIdx[target - num]];
        }
        pairIdx[num] = i;
    }    
};

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> pairIdx = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (pairIdx.containsKey(target - num)) {
                return new int[] { i, pairIdx.get(target - num) };
            }
            pairIdx.put(num, i);
        }
        return new int[] {};        
    }
}

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> pairIdx;
        for (int i = 0; i < nums.size(); ++i) {
            int num = nums[i];
            if (pairIdx.find(target - num) != pairIdx.end()) {
                return {i, pairIdx[target - num]};
            }
            pairIdx[num] = i;
        }
        return {};        
    }
};

🧮 計算量

• 時間計算量: $$O(n)$$
• 空間計算量: $$O(n)$$

英語版