JavaScriptで合計がKになる連続部分配列の個数を求める方法

はじめに

本記事では、第1引数として数値の配列、第2引数として単一の数値を受け取るJavaScript関数を作成します。この関数の役割は、「合計が第2引数で指定した値と一致する連続する部分配列(サブ配列)」の総数を数えて返すことです。

なお、配列内のすべての数値は正の数であることが保証されているものとします。この前提があるため、後述するスライディングウィンドウ法を非常に効率的に適用できます。

入力例

const arr = [1, 1, 1];
const sum = 2;

この場合、出力は 2 になります。配列 [1, 1, 1] の中には、合計が 2 になる連続部分配列がちょうど2つ存在するためです。

アプローチ:スライディングウィンドウ法

ここでは、left と right の2つのポインタを使って「条件を満たすウィンドウ(目的の合計を持つ部分配列)」を探索し、その個数をカウントするスライディングウィンドウアルゴリズムを採用します。

基本的な流れは次のとおりです。

• right ポインタを進めてウィンドウを右へ拡大し、合計に新しい要素を加算します。
• 合計がターゲットを超えたら、left ポインタを進めてウィンドウを左側から縮小します。
• 合計がターゲットと一致したら、カウンターを1増やします。

配列の要素がすべて正の数であるため、right を進めれば合計は必ず増加し、left を進めれば必ず減少します。この単調性のおかげで、すべての組み合わせを総当たりする O(n²) の方法ではなく、線形時間 O(n) で問題を解けます。

コード例

const arr = [1, 2, 3, 4, 5];
const sum = 5;

// スライディングウィンドウ(双ポインタ)で合計が target になる部分配列を数える
const findAll = (arr = [], target) => {
    let count = 0;
    let sum = 0;
    let left = 0;

    for (let right = 0; right < arr.length; right++) {
        // ウィンドウを右に拡張
        sum += arr[right];

        // 合計がターゲットを超えたら左側を縮小
        while (sum > target && left <= right) {
            sum -= arr[left];
            left++;
        }

        // 合計が一致したらカウント
        if (sum === target) {
            count++;
        }
    }
    return count;
};

console.log(findAll(arr, sum));
console.log(findAll([1, 1, 1], 2));

出力

コンソールには次のように表示されます。

2
2

処理の流れの解説

例として [1, 1, 1]、target = 2 の場合を追いかけてみましょう。

• right = 0 のとき:合計は 1。ターゲット未満のため何もしません。
• right = 1 のとき:合計は 2。ターゲットと一致したので count = 1。
• right = 2 のとき:合計は 3。ターゲットを超えたため左側を縮小して合計は 2 へ。再び一致したので count = 2。

最終的に 2 が返され、「合計が 2 になる部分配列が2つ存在する」という事実と一致します。同様に [1, 2, 3, 4, 5] の場合は [2, 3] と [5] の2つが該当します。

計算量

left と right はそれぞれ配列を高々一度ずつ走査するだけなので、時間計算量は O(n)、追加のメモリも不要で空間計算量は O(1) となります。各開始位置からすべての終了位置を試す素朴な総当たり法(O(n²))と比較して、大幅に効率的な実装です。