JavaScriptで合計が指定値と一致するバイナリ部分配列の個数を数える方法

問題

最初の引数としてバイナリ配列 arr を、2番目の引数として数値 target を受け取る JavaScript 関数を作成します。

この関数の役割は、配列 arr 内に存在する連続する部分配列のうち、要素の合計が target と一致するものの個数を数え、その結果を返すことです。

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

入力

const arr = [1, 0, 1, 0, 1];
const target = 2;

出力

const output = 4;

出力の説明

条件を満たす部分配列は、次の4つです。

[1,0,1]
[1,0,1,0]
[0,1,0,1]
[1,0,1]

解法のアプローチ：累積和とハッシュマップ

すべての部分配列を総当たりで調べる方法もありますが、その場合時間計算量は O(n²) となり、配列が長くなると非効率です。そこで累積和（プレフィックスサム）とハッシュマップを組み合わせることで、O(n) の線形時間に高速化できます。

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

• 変数 sum に、現在位置までの要素の累積和を保持します。
• map[sum] には「これまでに同じ累積和が出現した回数」を記録します。
• ある時点で累積和が S のとき、それより前に累積和が S − target であった箇所が存在すれば、その箇所の直後から現在位置までの部分配列の合計は必ず target になります。
• したがって count += map[sum - target] とすることで、条件を満たす部分配列の個数を効率的に加算できます。

なお、ループの先頭で map[sum] を更新してから sum を進めることで、「空の前置き（累積和 0）」も含めて正しくカウントできる仕組みになっています。

コード例

const arr = [1, 0, 1, 0, 1];
const target = 2;

const countSubarrays = (arr = [], target = 1) => {
   const map = {}
   let sum = 0
   let count = 0
   for (const num of arr) {
      // 現在の累積和の出現回数を記録
      map[sum] = (map[sum] || 0) + 1
      sum += num
      // 合計が target となる部分配列の個数を加算
      count += map[sum - target] || 0
   }
   return count
};

console.log(countSubarrays(arr, target));

出力

4

計算量について

• 時間計算量： O(n) ― 配列を一度だけ走査すればよいため非常に高速です。
• 空間計算量： O(n) ― 累積和の出現回数を保存するためのマップが必要です。

この手法はバイナリ配列だけでなく、負の数を含む整数配列に対しても同様に適用できる汎用的なテクニックなので、覚えておくとさまざまな場面で役立ちます。