JavaScriptで合計が0になる部分配列が存在するかどうかを判定する方法

正と負の値が混在する数値の配列を受け取り、元の配列の中に合計が0になる部分配列(サブ配列)が存在するかどうかを判定するJavaScript関数を作成する必要があります。

関数は、その判定結果に基づいてブール値(true または false)を返す必要があります。

アプローチ

この問題のアプローチはシンプルです。forループを使って配列を先頭から走査しながら、その要素までの累積和を計算していきます。走査の途中で累積和が0になった場合、あるいは以前に同じ値の累積和が出現した場合は、合計が0になる部分配列が存在することを意味します。逆に、配列の最後までそのような状況が一度も発生しなければ、合計が0になる部分配列は存在しないと判定できます。

累積和が同じ値に戻るということは、その間に加算された要素の合計が0であることを示しているためです。この性質を利用することで、効率的に判定を行えます。

それでは、この関数のコードを見てみましょう。

コード例

const arr = [4, 2, -1, 5, -2, -1, -2, -1, 4, -1, 5, -2, 3];
const zeroSum = arr => {
    const map = new Map();
    let sum = 0;
    for(let i = 0; i < arr.length; i++){
        sum += arr[i];
        if(sum === 0 || map.get(sum)){
            return true;
        };
        map.set(sum, i);
    };
    return false;
};
console.log(zeroSum(arr));

このコードでは、Map オブジェクトを使ってこれまでに出現した累積和を記録しています。各要素を加算した後、累積和が0であるか、すでにMapに登録済みの値と一致するかを確認し、該当すれば即座に true を返します。

出力

コンソールへの出力結果は次のとおりです。

true

この例の配列では、たとえば [2, -1, 5, -2, -1, -2, -1] のように合計が0になる部分配列が存在するため、関数は true を返します。このアルゴリズムの計算量はO(n)であり、すべての部分配列を総当たりで調べるO(n²)の方法と比べて大幅に効率的です。