JavaScriptで配列内のすべての奇数長サブ配列の合計を求める方法

本記事では、整数の配列を引数として受け取るJavaScript関数の作成方法を解説します。この関数は、元の配列から生成できる長さが奇数のすべてのサブ配列（部分配列）を列挙し、それらに含まれる全要素の合計値を計算して返すものです。

問題の概要

例として、次の入力配列を考えてみましょう。

const arr = [1, 2, 3];

この場合、期待される出力は次のとおりです。

const output = 12;

対象となる奇数長のサブ配列は [1]、[2]、[3]、[1, 2, 3] の4つであり、それぞれの合計を足し合わせると 1 + 2 + 3 + (1 + 2 + 3) = 12 となるためです。

解決アプローチ

ここでは、累積和（ランニングサム）を活用した効率的な手法を紹介します。考え方は以下のとおりです。

• 外側のループでサブ配列の開始位置 i を固定する。
• 内側のループで終端 j を順に伸ばしながら累積和を更新していく。
• サブ配列の長さ (j - i + 1) が奇数のときだけ、その時点の合計を結果に加算する。

ビット演算子 & 1 を使うことで偶奇判定を高速に行える点もポイントです。計算量は二重ループにより O(n²) となります。

実装コード

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

const arr1 = [1, 2, 3];
const arr2 = [1, 2, 3, 4, 5, 6];

const sumOfOddLengthSubarrays = (arr = []) => {
    let res = 0;
    for(let i = 0; i < arr.length; i++){
        let sum = 0;
        for(let j = i; j < arr.length; j++){
            sum += arr[j];
            // 長さが偶数の場合はスキップ
            if (((j - i + 1) & 1) === 0) {
                continue;
            };
            // 長さが奇数の場合のみ合計に加算
            res += sum;
        }
    };
    return res;
};

console.log(sumOfOddLengthSubarrays(arr1));
console.log(sumOfOddLengthSubarrays(arr2));

実行結果

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

12
98

1つ目の配列 [1, 2, 3] に対しては前述のとおり 12 が返ります。2つ目の配列 [1, 2, 3, 4, 5, 6] に対しては、長さ1のサブ配列6個・長さ3のサブ配列4個・長さ5のサブ配列2個の合計が計算され、98 という結果になります。

まとめ

累積和を用いることで、各サブ配列の合計を毎回ゼロから再計算することなく求められるため、シンプルかつ効率よく実装できます。配列の操作や部分配列に関する問題では頻出のテクニックなので、ぜひ覚えておきましょう。