# 题目

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. 简单来说就是找到一个数组中的等差数列的个数。

# 解题思路

```public int numberOfArithmeticSlices(int[] A) {
int len = A.length;
int[][] res = new int[len][len];
int count = 0;
//完成记录数组的初始化
for (int i = 0; i <= len - 3; i++) {
if (A[i + 1] - A[i] == A[i + 2] - A[i + 1]) {
res[i][i + 2] = 1;
count++;
}
}
for (int start = 0; start <= len - 3; start++) {
for (int end = start + 2; end < len - 1; end++) {
//状态的转化
if (res[start][end] == 1 && A[end + 1] - A[end] == A[end] - A[end - 1]) {
res[start][end + 1] = 1;
count++;
} else
break;
}
}
return count;
}```

```假如有一段等差数列是 1，2，3，4，5，6，7

```public int numberOfArithmeticSlices1(int[] A) {
int len = A.length;
if (len <= 2) return 0;
int start = 0;
int end = 1;
ArrayList<Integer> count = new ArrayList<>();
for (int i = 2; i < len; i++) {
//如果下一个元素满足等差数列的条件
if (A[i] - A[end] == A[end] - A[end - 1]) {
end++;
if(i==len-1)
} else {
//如果不满足，重置start与end,同时记录上一个满足的数列的长度
if (end - start + 1 >= 3)
start = end;
end = i;
}
}
int sum = 0;
for (int i : count) {
sum += ((i - 1) * (i - 2) / 2);
}
return sum;
}```

40 篇文章30 人订阅

0 条评论