413. Arithmetic Slices

一、题目简述

一个序列被称为是算术的，如果它至少包含三个元素，并且序列中任意两个相邻元素之差相同。 例如，以下序列是算术的：

1, 3, 5, 7, 9 7, 7, 7, 7 3, -1, -5, -9

以下序列不是算术的：

1, 1, 2, 5, 7

一个下标从零开始的数组A包含N个元素。使用整数对(P,Q)， 0≤P<Q<N ，来表示数组的一个片段。

数组的一个片段(P,Q)是算术的，如果满足：A[P],A[P+1],…,A[Q-1],A[Q]是算术的，并且P+1 < <script type="math/tex" id="MathJax-Element-227"><</script>Q。

函数返回数组A中算术片段的个数。 例如： A = [1, 2, 3, 4] 返回: 3,该数组含有的算术序列如下：[1, 2, 3], [2, 3, 4] 和 [1, 2, 3, 4]。

函数原型： int numberOfArithmeticSlices(vector<int>& A)

二、编程思路

该题可以使用动态规划思路进行求解，提供两种解题思路，第一种思路的时间复杂度为 O(N2) ，第二种思路的时间复杂度为 O(N) 。

2.1 简单思路

状态定义：令dp[i][j]表示数组A的A(i,j)片段是否为算术序列。 状态转移方程：

若i=j-2，则dp[i][j]=(2*A[i+1]==A[i]+A[j]);若i < <script type="math/tex" id="MathJax-Element-246"><</script>j-2，则dp[i][j]=dp[i][j-1]&&(2*A[j-1]==A[j]+A[j-2]);该状态转移方程较为容易理解，表示如果片段A(i,j-1)为算术序列，并且新加入的元素A[j]能与之前序列构成算术序列，则片段A(i,j)为算术的。之后统计A所有片段中算术片段的个数即可。

2.2 升级思路

由以上分析可以看出，2.1中的思路其实枚举了A的所有片段，之后判断其是否为算术片段。并且在递推式dp[i][j]=dp[i][j-1]&&(2*A[j-1]==A[j]+A[j-2]);中并未用到i的信息，因此可以考虑将问题简化为 O(N) 的复杂度。

状态定义：令dp[i]表示以i结尾的最长算术片段的长度。并且初始值均为2。 状态转移方程：若2 ∗ A[i-1]==A[i] A[i-2]，则dp[i]=dp[i-1] (2∗A[i-1]==A[i]+A[i-2])；否则，dp[i]=2;对于一个长度为len (len>2) 的算术片段，其包含的子算术片段的个数为： (len−1)∗(len−2)2 据此，避免重复情况，如，序列A={1, 2 ,3 ,4}，其dp={2, 2, 3, 4}，只应计算dp[3]=4的子片段数量。求出A中算术子片段的个数即可。

三、程序设计

3.1 简单思路

class Solution { public: int numberOfArithmeticSlices(vector<int>& A) { int size=A.size(); if(size<3) return 0; vector<vector<bool> >dp(size,vector<bool>(size,false)); int sum=0; for(int i=0;i<size;i++){ for(int j=i+2;j<size;j++){ if(j==i+2) dp[i][j]=(2*A[i+1]==A[i]+A[j]); else{ dp[i][j]=dp[i][j-1]&&(2*A[j-1]==A[j]+A[j-2]); } if(dp[i][j]) sum++; } } return sum; } };

3.2 升级思路

class Solution { public: int numberOfArithmeticSlices(vector<int>& A) { int size=A.size(); if(size<3) return 0; int start=0,sum=0; for(int i=2;i<size;i++){ int len=i-start+1; if(2*A[i-1]==A[i-2]+A[i]){ if(i==size-1 && len>2){ sum+=(len-1)*(len-2)/2; } }else{ len--; if(len>2) sum+=(len-1)*(len-2)/2; start=i-1; } } return sum; } };

四、参考资料

无