JavaScriptでソート済み配列から目標の合計値になる2つの数値を検索する方法

問題の概要

昇順にソートされた整数の配列が与えられているとします。ここで求められるのは、この配列を第1引数として、目標となる合計値（target）を第2引数として受け取るJavaScript関数を実装することです。

関数は、配列の中から「足し合わせると目標の合計値と一致する2つの数値」を見つけ出して返す必要があります。

この問題を解く上での制約条件は次のとおりです。

• 計算量は線形時間 O(n) であること
• 使用するメモリは定数空間 O(1) であること

解決アプローチ：ツーポインター法

配列がすでにソートされているという前提条件があるため、この問題はツーポインター（Two Pointers）と呼ばれるテクニックを使うことで効率的に解くことができます。

具体的な手順は以下の通りです。

1. 1つ目のポインタ left を配列の先頭に、2つ目のポインタ right を配列の末尾に配置します。
2. 両方のポインタが指す要素の合計を計算します。
3. 合計が目標値と一致した場合、その2つの要素が答えとなります。
4. 合計が目標値より大きい場合は、right を左へ移動させて合計を減らします。
5. 合計が目標値より小さい場合は、left を右へ移動させて合計を増やします。
6. ポインタが交差するまでこの処理を繰り返します。

この手法では各要素が最大1回しか参照されず、余分なデータ構造も不要なため、O(n)時間・O(1)空間という制約を満たすことができます。

サンプルコード

以下が実際のコード例です。

const arr = [4, 6, 8, 9, 11, 12, 18, 21];
const num = 27;
const findElements = (arr = [], target) => {
    let left = 0;
    let right = arr.length - 1;
    let res = [];
    while (left < right) {
        let leftElement = arr[left];
        let rightElement = arr[right];
        if (leftElement + rightElement === target) {
            res.push(arr[left]);
            res.push(arr[right]);
            break;
        } else if (leftElement + rightElement > target) {
            right--;
        } else {
            left++;
        }
    }
    return res;
};
console.log(findElements(arr, num));

実行結果

上記のコードを実行すると、コンソールには次のような出力が表示されます。

[6, 21]

この例では 6 + 21 = 27 となり、目標値と正しく一致していることが確認できます。このように、ツーポインター法を活用すれば、ソート済み配列に対するペア探索の問題をシンプルかつ高速に解決することが可能です。