C++プログラムで配列内の等差数列スライスを数える方法

「等差数列」とは、少なくとも3つの要素から構成され、隣り合う任意の2要素の差がすべて等しい数列のことです。例えば、[1, 3, 5, 7, 9]、[7, 7, 7, 7]、[3, -1, -5, -9] などは等差数列ですが、[1, 1, 2, 5, 7] は差が一定ではないため等差数列にはなりません。

問題の定義

N個の数からなる0始まりの配列Aが与えられます。この配列の「スライス」とは、0 <= P < Q < N を満たす整数のペア(P, Q)が表す部分配列のことです。スライス(P, Q)が表す数列 A[P], A[P+1], ..., A[Q-1], A[Q] が等差数列になっているとき、そのスライスを「等差数列スライス（arithmetic slice）」と呼びます。この記事では、配列Aに含まれる等差数列スライスの総数を求める関数を実装します。

例えば、入力が [1, 2, 3, 4] の場合、出力は 3 になります。[1, 2, 3]、[2, 3, 4]、そして [1, 2, 3, 4] の3つが等差数列スライスとして数えられるためです。

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

この問題は、動的計画法（DP）を使うと効率的に解けます。dp[i] を「インデックスiで終わる等差数列スライスの個数」と定義し、次の手順で答えを求めます。

• ret := 0、n := 配列Aのサイズ とし、サイズnの配列dpを用意する
• i を 2 から n - 1 までループする
  • A[i] - A[i-1] == A[i-1] - A[i-2] の場合（連続する3要素が等差関係にある場合）
    • dp[i] := 1 + dp[i-1] と更新する
    • ret に dp[i] を加算する
• 最後に ret を返す

この更新式のポイントは、「i番目で終わる新しい等差数列スライス」は必ず A[i-2], A[i-1], A[i] の3要素を含むという点です。i-1番目で終わるスライスが dp[i-1] 個あるなら、それらを1要素分伸ばしたものに加えて、新たな3要素のスライス1つが追加されるため、dp[i] = dp[i-1] + 1 となります。

C++での実装例

以下に実際の実装を示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numberOfArithmeticSlices(vector<int>& A) {
      int ret = 0;
      int n = A.size();
      vector<int> dp(n);
      for(int i = 2; i < n; i++){
         if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]){
            dp[i] = 1 + dp[i - 1];
            ret += dp[i];
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1, 2, 3, 4};
   cout << ob.numberOfArithmeticSlices(v);
}

入力

[1, 2, 3, 4]

出力

3

計算量

時間計算量は O(n)、空間計算量も O(n) です。なお、dp配列全体を保持する代わりに直前の値1つだけを変数で管理すれば、空間計算量を O(1) まで削減することもできます。