2つの数の和

2つ以上のユニークな数字の集合Aの中から、ターゲット(target)の数字の和となる数字のペアを見つけ出す。数字のペアは最大1つある。答えは値が小さい順に並べるとする。

例えばAが1, 10, 5, -1、12、targetが15であれば、答えは10, 5のペアである。Aを数字の配列の引数、targetを数字の引数としてこれを実装する。

アルゴリズム実装(1) O(n²)

最も簡単なアルゴリズムは二重ループして、すべての要素の和のパターンを出すこと。計算量はO(n^2)。使用しているsortは2つの数値の比較なので無視する。

function twoNumberSum(A, target) {    
    for (let i = 0; i < A.length; i++) {
            for (let j = 0; j < A.length; j++) {
                if (i === j) continue;
                if (A[i] + A[j] === target){
                    return [A[i], A[j]].sort((a, b) => a - b)
                }
            }
        }

        return [];
}

アルゴリズム実装(2) O(n)

計算し終えた要素を配列storeに保存していき、ワンループで済ます。計算量はO(n)

ループ中の数値をxとすると、ペアになる可能性のある数値yはtarget - xと表せる。storeにyが存在しなければ、xをstoreに保存する。

こちらも使用しているsortは2つの数値の比較なので無視する。

function twoNumberSum(A, target) {    
        const store = []

        for (const x of A) {
            const y = target - x
            if (store.includes(y)) {
                return [x, y].sort((a, b) => a - b)
            } else {
                store.push(x)
            }
        }

        return [];
}

includesの実装が気になる。ハッシュテーブルに保存のほうがいいかも？

アルゴリズム実装(3) O(n log n)

まず、Aを小さい順に並び替える。ソートに関しては、JavaScriptの実装はブラウザにもよるがここではクイックソート、計算量O(n log n)とする。

[-1, 1, 5, 10, 12]

現在の最小の値のインデックスをmin、最大の値のインデックスをmaxとおくと

sum = array[left] + array[right]

となる。sumがtargetより大きい場合、値を小さくしたいのでrightを小さくする。逆にsumがtargetより小さい場合、値を大きくしたいので、leftを小さくする。

例えば初期状態でleft=0、right=4であるためsum=11

left          right
  |             |
[-1, 1, 5, 10, 12]

targetはそれより大きいのでleftを右に動かしてleft=1、right=4ならばsum=13

    left      right
     |          |
[-1, 1, 5, 10, 12]

targetはそれより大きいのでleftを右に動かしてleft=2、right=4ならばsum=17

       left   right
        |       |
[-1, 1, 5, 10, 12]

targetはそれより小さいのでrightを左に動かしてleft=2、right=3ならばsum=15

      left right
        |   |
[-1, 1, 5, 10, 12]

クイックソートと一回のループの計算量は

O(n log n) + O(n) = O (n log n)

であることからO(n log n)

答えのペアはユニークな数値となることに注意してこれを実装すると

function twoNumberSum(A, target) {    
    A.sort((a, b) => a - b)
    let left = 0
    let right = A.length - 1
    while (left < right) {
        const sum = A[left] + A[right]
        if (sum === target) {
            return [A[left], A[right]]
        } else if (sum < target) {
            left++
        } else if (sum > target) {
            right--
        }
    }
    return [];
}