JavaScriptで合計がkの倍数となる長さ2以上の連続部分配列を判定する方法

問題

整数の配列 arr を第一引数に、単一の整数 target を第二引数として受け取る JavaScript 関数を作成します。この関数は、長さが少なくとも 2 以上である連続する部分配列（サブアレイ）の中に、要素の合計が target の倍数（すなわち n × target、n は任意の整数）となるものが存在するかどうかを判定します。

条件を満たす部分配列が存在すれば true を、存在しなければ false を返します。

たとえば、関数への入力が次の場合を考えてみましょう。

const arr = [23, 2, 6, 4, 7];
const target = 6;

このとき、出力は次のようになります。

const output = true;

出力の解説

[23, 2, 6, 4, 7] 全体は長さ 5 の連続部分配列であり、その合計は 42（= 6 × 7）です。42 は 6 の倍数であるため、条件を満たしていることがわかります。

解法のアプローチ：累積和の剰余を活用

この問題は、累積和（プレフィックスサム）の剰余をハッシュマップに記録することで、O(n) の時間計算量で効率的に解くことができます。

考え方のポイントは次の通りです。

• 配列を左から順に走査し、そこまでの累積和を求めます。
• target が 0 以外の場合、累積和を target で割った余りに置き換えます。
• 同じ余りが過去にも出現していれば、その間の部分配列の合計は必ず target の倍数になります（差分の剰余が 0 になるため）。
• ハッシュマップには各余りが最初に出現したインデックスを記録し、あらかじめ hash[0] = -1 と初期化しておくことで、「配列の先頭から始まる部分配列」も正しく処理できるようにします。
• 現在のインデックスと記録済みインデックスの差が 1 より大きければ、該当する部分配列の長さは 2 以上であるため、true を返せます。

実装コード

上記のロジックを実装したコードがこちらです。

const arr = [23, 2, 6, 4, 7];
const target = 6;
const checkSubarraySum = (arr = [], target = 1) => {
    let sum = 0
    const hash = {}
    hash[0] = -1;
    for (let i = 0; i<arr.length; i++) {
        sum += arr[i]
        if (target!=0) sum %= target
        if ( hash[sum] !== undefined ) {
            if(i-hash[sum]>1) return true
        } else {
            hash[sum] = i
        }
    };
    return false;
};
console.log(checkSubarraySum(arr, target));

出力

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

true

まとめ

すべての部分配列を総当たりで調べる O(n²) のアプローチと比べ、剰余の一致をハッシュマップで検出するこの手法は大幅に効率的です。また、target が 0 の場合にも対応しており、その際は剰余計算をスキップして累積和そのもので判定を行う仕組みになっています。累積和と剰余の性質を組み合わせることで、一見複雑な問題を線形時間で解決できる好例と言えるでしょう。