Leetcode 413. Arithmetic Slice 算术序列切片(动态规划，暴力)
题目描述
如果一个数组1.至少三个元素2.两两之间差值相同，那么这个数组就是算术序列
比如下面的数组都是算术序列：
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
但是这一个就不是：
1, 1, 2, 5, 7
求给定数组，能有多少个算术序列
测试样例
Input: [1, 2, 3, 4]
Output: 3
有三个算术序列切片：
[1,2,3], [2,3,4], [1,2,3,4]
注意，切片是不能跳着选的...
详细分析
暴力：
从长度3开始直到数组那么长，每次暴力求[k,k+len]是否是算术序列（是否两两差值相同）即可。动态规划：
对于[1,2,3,4,3,5,6]，我们从3开始:
- [1,2,3]是一个算术序列，dp[2]=1
- 然后继续[2,3,4],是算术序列则dp[3]=dp[2]+1;
- 继续[3,4,3]不是算术序列,dp[4]=0
- 继续[4,3,5] dp[5]=0
- [3,5,6] dp[6]= 0
算法实现
- 方法1：暴力
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
if(A.size()<3){
return 0;
}
int totalSolution = 0;
for(int dist=3;dist<=A.size();dist++){
for(int k=0;k+dist<=A.size();k++){
// Arithmetic sequence checking for current [k,k+distance] (sub)sequence
bool isArithmeticSeq = true;
int diff = A[k+1] - A[k];
for(int p=k+2;p<k+dist;p++){
if((A[p]-A[p-1])!=diff){
isArithmeticSeq = false;
break;
}
}
if(isArithmeticSeq) totalSolution++;
}
}
return totalSolution;
}
};
- 方法2：DP
class Solution {
public int numberOfArithmeticSlices(int[] A) {
int[] dp = new int[A.length];
int sum = 0;
for(int i=2;i<A.length;i++){
if( (A[i]-A[i-1]) == (A[i-1]-A[i-2]) ){
dp[i]=dp[i-1]+1;
sum +=dp[i];
}else{
dp[i]=0;
}
}
return sum;
}
}