LeetCode - Two Sum

LeetCode の Two Sum を解いてみます。

問題の概要

• インプット（引数）
  • 数値の配列とターゲットの数値
• アウトプット（戻り値）
  • 与えられた配列の数値を足し合わせてターゲットの数値と一致する２つの数値の組み合わせ。その２つの数値のインデックスを配列で返す。
• 補足
  • 与えられる数値群から必ず一意に答えが得られると仮定してよい。同じ要素は二度使用しない。

Brute Force

ブルートフォース（総当たり）のアプローチでやると以下のようになります。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int complement; 
        for (int x = 0; x < nums.length; x++) {  
            complement = target - nums[x];
            for (int y = 0; y < nums.length; y++) { 
                //同じ値は利用しないので除外する（次に処理を移す）
                if (x == y) { 
                    continue;
                } 
                if (nums[y] == complement) {
                    return new int[] {x, y};
                }
            }            
        }
        throw new IllegalStateException("params is invalid");
    }
}

これだと、Status = Accepted, Runtime = 36ms, Memory = 37.5 MB という結果になりました。

One-pass Hash Table

候補となる数値を見つけながら順次HashMapに値を格納していくやり方です。

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // key=加算の候補の数値, その数値が格納されていた配列上のindex
        Map<Integer, Integer> map = new HashMap<>();
        map.put(nums[0], 0);  // numsの最初の数値だけでは絶対に答えは求まらないのでとりあえずHashMapに格納する

        int complement;
        for (int i = 1; i < nums.length; i++) {
            complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] {i, map.get(complement)};
            }
            map.put(nums[i], i);
        }
        throw new IllegalStateException("params is invalid");
    }
}

これだと、Status = Accepted, Runtime = 2ms, Memory = 37.3 MB という結果になりました。

総当たりでやるよりも効率的です。

他にも Two-pass Hash Table というやり方もあります。具体的な解説は LeetCode の Solution を読んでもらった方が良いです。

---

関連サイト