# 413. Arithmetic Slices 等差数列划分

@TOC

## # 题目描述

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.

1, 1, 2, 5, 7


A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence: A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

A = [1, 2, 3, 4]


return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

## # 解题方法

### # 暴力

C++ 代码如下：

class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
const int N = A.size();
int res = 0;
for (int i = 0; i < N - 2; i++) {
for (int j = i + 1; j < N; j++) {
if (isArithmetic(A, i, j))
res ++;
}
}
return res;
}
private:
bool isArithmetic(vector<int>& A, int start, int end) {
if (end - start < 2) return false;
for (int i = start; i < end - 1; i++) {
if (A[i + 1] * 2 != A[i] + A[i + 2])
return false;
}
return true;
}
};

• 时间复杂度：，遍历所有的子数组，需要有两重循环，时间复杂度是 ；判断每个子数组是不是等差数列，时间复杂度是 ；所以总的时间复杂度是
• 空间复杂度：

### # 双指针

• 其实，如果我们已经知道一个子数组的前面部分不是等差数列以后，那么后面部分就不用判断了。
• 同时，我们知道等差数列的所有的相邻数字的差是固定的。

C++ 代码如下，

class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
const int N = A.size();
int res = 0;
for (int i = 0; i < N - 2; i++) {
int d = A[i + 1] - A[i];
for (int j = i + 1; j < N - 1; j++) {
if (A[j + 1] - A[j] == d)
res ++;
else
break;
}
}
return res;
}
};

• 时间复杂度：
• 空间复杂度：

### # 递归

A[0, end]内的end作为终点的等差数列的个数，相当于在 A[0, end - 1]的基础上，增加了 A[end] 。 ​

1. A[end] - A[end - 1] == A[end - 1] - A[end - 2]时，说明增加的A[end]能和前面构成等差数列，那么 slices(A, end) = slices(A, end - 1) + 1
2. A[end] - A[end - 1] != A[end - 1] - A[end - 2]时， 说明增加的 A[end]不能和前面构成等差数列，所以slices(A, end) = 0；

class Solution(object):
def numberOfArithmeticSlices(self, A):
N = len(A)
self.res = 0
self.slices(A, N - 1)
return self.res

def slices(self, A, end):
if end < 2: return 0
op = 0
if A[end] - A[end - 1] == A[end - 1] - A[end - 2]:
op = 1 + self.slices(A, end - 1)
self.res += op
else:
self.slices(A, end - 1)
return op

• 时间复杂度：。因为递归函数最多被调用 N 次，每次调用的时候都需要向前遍历一次。
• 空间复杂度：，递归栈的最大深度是 N。

### # 动态规划

1. A[i] - A[i - 1] == A[i - 1] - A[i - 2]时，说明增加的A[i]能和前面构成等差数列，那么 dp[i] = dp[i - 1] + 1
2. A[i] - A[i - 1] != A[i - 1] - A[i - 2]时， 说明增加的 A[i]不能和前面构成等差数列，所以dp[i] = 0；

class Solution(object):
def numberOfArithmeticSlices(self, A):
N = len(A)
dp = [0] * N
for i in range(1, N - 1):
if A[i - 1] + A[i + 1] == A[i] * 2:
dp[i] = dp[i - 1] + 1
return sum(dp)

• 时间复杂度：
• 空间复杂度：

class Solution(object):
def numberOfArithmeticSlices(self, A):
count = 0
k = 0
for i in xrange(len(A) - 2):
if A[i + 1] - A[i] == A[i + 2] - A[i + 1]:
k += 1
count += k
else:
k = 0
return count

• 时间复杂度：
• 空间复杂度：

## # 日期

2018 年 2 月 28 日 2018 年 12 月 10 日 —— 又是周一！ 2021 年 8 月 10 日 —— 昨天开车去了雁栖湖