413 Arithmetic Slices
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.
分析&代码
我自己的写法觉得有点蠢……先把每个相邻数之间差算出来，然后再走一遍，如果有n(n>=2)连续的相等的数，那么可以组成的组合就是(n-2)+(n-3)+..+1
public int numberOfArithmeticSlices(int[] A) {
if(A.length < 3) {
return 0;
}
int len = A.length;
int[] dif = new int[len - 1];
for(int i = 0; i < len - 1; i++) {
dif[i] = A[i + 1] - A[i];
}
int cnt = 1;
int res = 0;
for(int i = 1; i < len - 1; i++) {
if(dif[i-1] == dif[i]) {
cnt++;
} else {
if(cnt >= 2) {
for(int j = cnt - 1; j >= 1; j--) {
res += j;
}
}
cnt = 1;
}
}
if(cnt >= 2) {
for(int j = cnt - 1; j >= 1; j--) {
res += j;
}
}
return res;
}
看了下别人的，其实道理倒是一样的，不过写起来好看多了
public int numberOfArithmeticSlices(int[] A) {
int curr = 0, sum = 0;
for (int i=2; i<A.length; i++)
if (A[i]-A[i-1] == A[i-1]-A[i-2]) {
curr += 1;
sum += curr;
} else {
curr = 0;
}
return sum;
}