# 2 Different AC JAVA Solution, Using Two Pointer and DP

• DP is my first idea for this problem, it is based on the rules:

if we want to find out whether [a,b,c,d] is arithmetic, we just need to find out the result of ([a,b,c] is arithmetic) && (d-c == c-b), Here comes to DP Solution:

``````public int numberOfArithmeticSlices(int[] A) {
int count = 0;
boolean[][] dp = new boolean[A.length][A.length];
for (int i = 0; i < A.length-2; i++) {
if ((A[i+2]-A[i+1]) == (A[i+1]-A[i])) {
dp[i][i+2] = true;
count++;
}
}
for (int k = 3; k < A.length; k++){
for (int i = 0; i < A.length-k; i++){
dp[i][i+k] = (dp[i][i+k-1] && (A[i+k]-A[i+k-1] == A[i+1]-A[i]));
if (dp[i][i+k]) count++;
}
}
return count;
}
``````

Although DP can get the right answers, it is too slow, O(n2).

The second idea is to search from the largest arithmetic slices, if [a,b,c,d,e] is arithmetic, all its subset (length >= 3) must be arithmetic. the total number of the arithmetic subsets will be (5-1)(5-2)/2. To achieve that, we just use two pointers to monitor the start and the end of the arthmetic slices, Here comes the code:

``````public int numberOfArithmeticSlices(int[] A) {
int count = 0;
int tempLength = 0, i = 0, ptr = 2;
while (i < A.length-2){
if (ptr < A.length && (A[i+1]-A[i]) == (A[ptr]-A[ptr-1]))
ptr++;
else{
tempLength = ptr-i;
if (tempLength != 2 || (A[i+2] - A[i+1]) == (A[i+1]-A[i]))
count += ((tempLength-1)*(tempLength-2) / 2);
int temp = i;
i = ptr-1; ptr = i+2;
}
}
return count;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.