JavaScriptで積がターゲット未満となる部分配列の個数を数える方法

問題

数値の配列 arr を第1引数に、数値 target を第2引数として受け取るJavaScript関数を作成する必要があります。

この関数は、部分配列に含まれるすべての要素の積が target よりも小さくなる「連続した」部分配列の個数を数えて返すものです。

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

入力

const arr = [10, 5, 2, 6];
const target = 100;

出力

const output = 8;

出力の説明

積が100未満となる8つの部分配列は次のとおりです。

[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]

なお、[10, 5, 2] は積がちょうど100となり、「100より厳密に小さい」という条件を満たさないため、カウントには含まれません。

解き方のポイント：スライディングウィンドウ法

すべての部分配列を総当たりで調べると計算量が大きくなり、配列が長くなるほど非効率です。そこで役立つのがスライディングウィンドウ（二重ポインタ）法です。

配列の要素が正の整数である場合、ウィンドウの右端 right を1つずつ拡大しながら、積が target 以上になったら左端 left を進めてウィンドウを縮小します。これにより、各右端に対する有効な部分配列の個数を定数時間で求められます。

右端が right のとき、条件を満たす部分配列の始点は left から right の間のいずれかなので、その個数は right - left + 1 になります。これをすべての right について合計すると答えが得られます。

コード例

以下が実際のコードです。

const arr = [10, 5, 2, 6];
const target = 100;
const countSubarrays = (arr = [], target = 1) => {
   let product = 1
   let left = 0
   let count = 0
   for (let right = 0; right < arr.length; right++) {
      product *= arr[right]
      while (left <= right && product >= target) {
         product /= arr[left]
         left += 1
      }
      count += right - left + 1
   }
   return count
};
console.log(countSubarrays(arr, target));

アルゴリズムの流れ

1. 初期化： ウィンドウ内の積を保持する product を1、左端 left を0、カウンター count を0に設定します。
2. ウィンドウの拡大： 右端 right を順に進めながら、product に arr[right] を掛けます。
3. ウィンドウの縮小： 積が target 以上になった場合は、積が target 未満になるまで左端の要素で割りながら left を進めます。
4. カウント： 各ステップで、右端が right である有効な部分配列の個数 right - left + 1 を count に加算します。

出力

8

計算量

時間計算量： O(n)。左右のポインタはそれぞれ最大でも配列の長さ分しか移動しないため、全体を線形時間で処理できます。
空間計算量： O(1)。追加のデータ構造は不要で、少数の変数だけで処理が完結します。