LeetCode #1 Two Sum を HashMap で解くときのポイントと実行速度の差について

問題

配列 nums と整数 target が与えられたとき、
足して target になる 2 つの要素のインデックスを返す。

回答①（containsValue() を使用した例）

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] array = new int[2];

        for (int i = 0; i < nums.length; i++) {
            map.put(i, nums[i]);
            array[0] = i;

            if (map.containsValue(target - map.get(i))) {
                int index = getIndex(map, target - map.get(i));
                array[1] = index;

                if (array[0] != array[1]) break;
            }
        }

        return array;
    }

    private int getIndex(HashMap<Integer, Integer> map, int key) {
        for (int k : map.keySet()) {
            if (map.get(k) == key) return k;
        }
        return 0;
    }
}

実行結果

項目	値
Runtime	309 ms
Memory	47.29 MB

問題点

containsValue() は内部で 全要素を線形検索するため O(n)。
さらに for の中で毎回呼ばれているため、全体で O(n²) になる。

回答②（containsKey() を使用した最適解）

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int num = target - nums[i];

            if (map.containsKey(num)) {
                return new int[] { map.get(num), i };
            }

            map.put(nums[i], i);
        }

        throw new IllegalArgumentException("No solution");
    }
}

実行結果

項目	値
Runtime	2 ms
Memory	47.10 MB

改善点の説明

メソッド	計算量	挙動
containsValue()	O(n)	値を全走査する
containsKey()	O(1)	HashMap の構造上 直接アクセスできる

つまり、HashMap は「値」ではなく「キー」で検索する構造。
正しく使うことで 計算量 O(n) → O(1) に改善できる。

補足：例外処理について（throw new IllegalArgumentException の理由）

LeetCode では 解が必ず存在する前提なので例外には到達しないが、
保険として例外を入れる場合は 非チェック例外 を使用するのが適切。

チェック例外と非チェック例外の違い

種類	例	特徴
チェック例外	IOExceptionなど	throws または try-catch が必須
非チェック例外	IllegalArgumentException, RuntimeException	メソッド宣言に書かなくてよい

設計上のポイント

スタックトレースを 呼び出し元（main など） でまとめて処理したい場合は、
サブクラスでは throws で例外を伝播し、main で try-catch する。

逆に、サブクラスで try-catch してしまうと、例外がそこで「消えて」しまい、
上位で状況が追えなくなる。

まとめ

containsValue() は 線形探索 → 遅い
containsKey() は O(1) → Two Sum では必須
LeetCode では非チェック例外で OK
例外は 上位でまとめて扱う設計が保守性が高い