JavaScriptで配列から作れる等差数列（AP）の個数を数える方法

等差数列（AP）とは

等差数列（Arithmetic Progression：AP）とは、隣り合う2つの数の差が常に一定の値になる数列のことです。この一定の差は「公差」と呼ばれます。

例えば、1, 2, 3, 4, 5, 6… という数列は、公差が1（2 − 1 = 1）の等差数列です。

問題

ここでは、整数の配列 arr を唯一の引数として受け取るJavaScript関数を作成します。

関数の役割は、その配列の中から作成可能な「サイズ3の等差数列」の個数を返すことです。各等差数列において、要素間の差はすべて同じでなければなりません。なお、入力配列は昇順にソートされていることが保証されています。

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

入力

const arr = [1, 2, 3, 5, 7, 9];

出力

const output = 5;

出力の説明

求められる等差数列は、以下の5つだからです。

[1, 2, 3]、[1, 3, 5]、[1, 5, 9]、[3, 5, 7]、[5, 7, 9]

アルゴリズムの考え方

この問題は、三重ループを使ってシンプルに解くことができます。

• 外側のループで、等差数列の最初の要素 arr[i] を選びます。
• 次のループで、3番目の要素 arr[k] を選びます。
• arr[i] と arr[k] の合計が偶数であれば、その平均値（(arr[i] + arr[k]) / 2）が中間の値になります。
• i と k の間にその中間値と一致する要素が存在すれば、それはサイズ3の等差数列を構成しているため、カウントを1つ増やします。

コード例

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

const arr = [1, 2, 3, 5, 7, 9];
const countAP = (arr = []) => {
    let i, j, k;
    let { length: len } = arr;
    let count = 0;
    for (i = 0; i < len - 2; i++){
        for (k = i + 2; k < len; k++){
            let temp = arr[i] + arr[k];
            let div = temp / 2;
            if ((div * 2) == temp){
                 for (j = i + 1; j < k; j++){
                     if (arr[j] == div){
                         count += 1;
                     }
                 }
            }
        }
    }
    return count;
};
console.log(countAP(arr));

出力

5

コードのポイント

(div * 2) == temp という条件チェックは、両端の要素の和が偶数であるかどうかを確認しています。奇数の場合、平均値は整数にならず、整数配列の中間要素として存在し得ないためです。また、配列が昇順にソートされていることを利用することで、中間要素を効率的に探索できます。計算量は O(n³) ですが、小規模な配列であれば十分実用的なアプローチです。