Arithmetic Slice

From http://codesays.com/2014/solution-to-count-arithmetic-sequence/
There is another question related to Arithmetic Sequence Longest Arithmetic Sequenece

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]

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 要算上每一个子集。遍历的时候追溯直到不能形成等差数列为止。

 算法复杂度是O(n)， space O(1)。

 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;  
   }