Pythonで数値リストから等差部分列の個数を求めるプログラム

数値のリスト nums が与えられたとき、長さ3以上の等差部分列（算術サブシーケンス）の個数を求める問題を考えてみましょう。等差数列とは、隣り合う数同士の差がすべて等しい数列のことです。

例えば、入力が nums = [6, 12, 13, 8, 10, 14] の場合、出力は 3 になります。これは、[6, 8, 10]、[6, 10, 14]、[12, 13, 14] という3つの等差部分列が存在するためです。

解法のアプローチ：動的計画法（DP）

この問題は、動的計画法を使って効率的に解くことができます。各インデックスと公差（差分）の組み合わせごとに、そこで終わる等差部分列の個数を記録していくのがポイントです。

具体的な手順は以下の通りです。

• dp := 新しいマップ（辞書）を作成

• n := nums のサイズ

• res := 0（答えを格納する変数）

• i を 0 から n まで繰り返す：

  • j を 0 から i まで繰り返す：

    • diff := nums[i] - nums[j]（公差を計算）

    • prev := dp[(i, diff)]、存在しない場合は 0

    • prevprev := dp[(j, diff)]、存在しない場合は 0

    • dp[(i, diff)] := prev + prevprev + 1

    • res := res + prevprev

• res を返す

仕組みの解説

ペア (j, i) に対して公差 diff を計算するとき、dp[(j, diff)] は「インデックス j で終わり、公差が diff である等差部分列の個数」を表します。これらの部分列に nums[i] を連結すると長さが1つ増えた新しい等差部分列になるため、その個数（prevprev）を答え res に加算します。これにより、長さ3以上の等差部分列だけが正確にカウントされます。

Pythonコード例

class Solution:
    def solve(self, nums):
        dp = {}
        n = len(nums)
        res = 0
        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]

                prev = dp.get((i, diff), 0)
                prevprev = dp.get((j, diff), 0)
                dp[(i, diff)] = prev + prevprev + 1

                res += prevprev
        return res

ob = Solution()
nums = [6, 12, 13, 8, 10, 14]
print(ob.solve(nums))

入力

[6, 12, 13, 8, 10, 14]

出力

3

このアルゴリズムの計算量は、二重ループを使用するため O(n²) となり、空間計算量も O(n²) です。リストの要素数がそれほど大きくない場合に、効率的かつシンプルに等差部分列を数えることができます。