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