Two Sum（2つの数の和）

まず、具体的な例を見る

[2, 7, 11, 15]の中から、足すと9になる二つの数を探してみます。2と7を足すと9になるため、条件に合うのは0番目の2と1番目の7です。

この一例だけなら、答えはすでに分かっています。決まった答えを返すだけなので、アルゴリズムを考える必要はありません。

数値が毎回変わる場合を考える

実際のプログラムでは、配列numsと目標値targetの内容は、実行するまで分かりません。

そこで、どのような数値が渡されても、合計がtargetになる二つを見つけられる共通の手順が必要になります。この共通の処理手順がアルゴリズムです。

一つの位置を二回選ぶことはできません。ただし、同じ数が別々の位置に入っていれば、その二つは選べます。この課題では、条件に合う組が必ず一つ存在するものとして扱います。

難しいのは、組み合わせの探し方

数が四つだけなら、組み合わせを一つずつ確認してもすぐに見つかります。しかし、数が10,000個になると、二つの組み合わせは最大49,995,000通りになります。すべての組み合わせを調べるのか、それまでに見た値を記録して必要な相手だけを探すのかによって、処理量が大きく変わります。

このページでは、LeetCodeのTwo Sumを題材にします。解き方の暗記ではなく、Arrayによる全探索とHashMapによる検索を比較し、処理時間と追加メモリのどちらを優先するか考えることが目的です。

基準となるArrayの全探索

最も単純なのは、二つの要素の組合せを順番にすべて確認する方法です。理解しやすく追加メモリもほとんど使いませんが、要素数が増えると比較回数が大きく増えます。

Kotlin

fun twoSumBruteForce(nums: IntArray, target: Int): IntArray {
    for (left in nums.indices) {
        for (right in left + 1 until nums.size) {
            if (nums[left] + nums[right] == target) {
                return intArrayOf(left, right)
            }
        }
    }

    error("条件に合う組が見つかりません")
}

時間計算量

O(n²)

空間計算量

O(1)

HashMapで探索を減らす

現在の値がvalueなら、必要な相手はtarget - valueです。それまでに見た値と位置をHashMapへ保存しておけば、必要な相手を平均O(1)で探せます。

Kotlin

fun twoSum(nums: IntArray, target: Int): IntArray {
    val indexByValue = mutableMapOf<Int, Int>()

    for ((index, value) in nums.withIndex()) {
        val needed = target - value
        val neededIndex = indexByValue[needed]

        if (neededIndex != null) {
            return intArrayOf(neededIndex, index)
        }

        indexByValue[value] = index
    }

    error("条件に合う組が見つかりません")
}

現在の値を登録する前に必要な相手を検索することで、同じ位置の要素を二回使うことを防ぎます。同じ値が複数ある場合でも、先に登録した別の位置は利用できます。