Non-Leetcode Questions: Arithmetic Slice
Arithmetic Slice, is a slice of an array num[i..j] with at least size 3 and has num[i], num[i+1]...num[j-1],num[j] forming an arithmetic sequence.
For example:
O(n) time complexity is required. Once the number of Arithmetic Slice is greater than 1000000000, return -1.
Naive Thinking:这道题一开始的例子给的好烦人，最好自己写一两个例子。
[1 2 3] has 1 arithmetic slice
[1 2 3 4] has 3 arithmetic slice since [1 2 3], [2 3 4] and [1 2 3 4].
这样就很清楚了，如果再来个[1 2 3 4 5]， 那就有6个了，就是连续的差等数列会使得count 要算上每一个子集。遍历的时候追溯直到不能形成等差数列为止。
Arithmetic Slice, is a slice of an array num[i..j] with at least size 3 and has num[i], num[i+1]...num[j-1],num[j] forming an arithmetic sequence.
For example:
Input:
[-1, 1, 3, 3, 3, 2, 1, 0]
Output:
5
Explanation:
There are five arithmetic sequences in the input:
[-1, 1, 3], [3, 3, 3], [3, 2, 1], [2, 1, 0], and [3, 2, 1, 0]
Naive Thinking:这道题一开始的例子给的好烦人，最好自己写一两个例子。
[1 2 3] has 1 arithmetic slice
[1 2 3 4] has 3 arithmetic slice since [1 2 3], [2 3 4] and [1 2 3 4].
这样就很清楚了，如果再来个[1 2 3 4 5]， 那就有6个了，就是连续的差等数列会使得count 要算上每一个子集。遍历的时候追溯直到不能形成等差数列为止。
public static final int limit = 1000000000;
public int getLAS(int[] A){
int count = 0;
// edge case
if(A.length <= 2) return count;
// main process
int i = 1;
while(i+1 < A.length){
int k = i+1;
// if its neighbor and itself form an AS, count++
if(2*A[i] == A[i-1]+A[k]){
count++;
if(count > limit) return -1;
// if two neighbors match, go through all the way until not match
while(k+1 < A.length && 2*A[k] == A[k-1]+A[k+1]){
k++;
count += (k-i);
if(count > limit) return -1;
}
}
// increment
i = k;
}
return count;
} 