2つの数の和
2つの数の和
2つ以上のユニークな数字の集合A
の中から、ターゲット(target
)の数字の和となる数字のペアを見つけ出す。数字のペアは最大1つある。答えは値が小さい順に並べるとする。
例えばA
が1, 10, 5, -1、12、target
が15であれば、答えは10, 5のペアである。A
を数字の配列の引数、target
を数字の引数としてこれを実装する。
アルゴリズム実装(1) O(n2)
最も簡単なアルゴリズムは二重ループして、すべての要素の和のパターンを出すこと。計算量は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 []; }