【JavaScript】合計が指定した数値に一致するすべての部分配列をスライディングウィンドウアルゴリズムで検索する方法

問題の概要

数値の配列と1つの数値が与えられたとき、第2引数として渡された数値と合計が一致するすべての部分配列を配列として返す関数を作成するのが今回の課題です。

たとえば、次のような入力を考えてみましょう。

const arr = [23, 5, 1, 34, 12, 67, 9, 31, 6, 7, 27];
const sum = 40;
console.log(requiredSum(arr, sum));

この場合、期待される出力は次の通りです。

[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]

これら3つの部分配列は、いずれも要素を足し合わせると40になるためです。

スライディングウィンドウアルゴリズム（線形時間）とは

スライディングウィンドウアルゴリズムは、配列の中から特定の条件を満たす部分配列を探したり、文字列から条件を満たす部分文字列を探したりする場面でよく使われる定番の手法です。今回の問題は、まさにこのアルゴリズムが最適にはまる典型例と言えます。

名前が示す通り、このアルゴリズムでは「ウィンドウ」と呼ばれる領域を作ります。ウィンドウの実体は元の配列の一部分（部分配列）です。このウィンドウを広げたり狭めたりしながら「安定状態」を目指していきます。

ここでいう「安定状態」とは、問題で指定された条件（今回は合計が特定の数値に一致すること）を満たしている状態のことです。条件を満たした時点でそのウィンドウを記録し、さらにスライドを続けます。多くのケースでは、ウィンドウを左端から開始し、右端が配列や文字列の末尾に到達するまでスライドさせ続けるのが基本の流れです。

コード例

それでは、実際のコードを見ていきましょう。

const arr = [23, 5, 1, 34, 12, 67, 9, 31, 6, 7, 27];
const sum = 40;

const findSub = (arr, sum) => {
    const required = [];
    for(let start = 0, end = 0, s = 0; end <= arr.length || s > sum ; ){
        if(s < sum){
            // 合計が目標より小さい → ウィンドウを右へ広げる
            s += arr[end];
            end++;
        }else if(s > sum){
            // 合計が目標より大きい → 左側を縮める
            s -= arr[start];
            start++;
        }else{
            // 条件を満たした → 結果に記録して1つずらす
            required.push(arr.slice(start, end));
            s -= arr[start];
            s += arr[end];
            start++;
            end++;
        };
    };
    return required;
};

console.log(findSub(arr, sum));

変数startとendは、それぞれの時点におけるウィンドウの開始位置と終了位置を表しています。

最初は両方とも0から始まります。現在の合計が目標値より小さい場合はウィンドウを右方向へ拡大し、大きい場合は左側を縮めます。そして合計がちょうど目標値と一致した瞬間に、その部分配列を結果配列へ追加し、ウィンドウ全体を1つ分右へ移動させます。これを末尾まで繰り返すことで、条件を満たすすべての部分配列を取りこぼしなく見つけられます。

実行結果

このコードをコンソールで実行すると、次の出力が得られます。

[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]

計算量と注意点

このアルゴリズムの時間計算量はO(n)（線形時間）です。各要素は最大でも1回ウィンドウに追加され、1回削除されるだけなので、すべての組み合わせを総当たりで調べるO(n²)のアプローチに比べて大幅に高速です。

ただし、スライディングウィンドウが正しく機能するためには、配列の要素がすべて正の数であることが前提となります。負の数が含まれる場合は、ウィンドウを縮めても合計が単調に減少するとは限らず、「累積和（プレフィックスサム）＋ハッシュマップ」など別の手法を検討する必要があるので注意しましょう。