# java solution Beat 100%, idea from Frog Jump

• The same idea with Frog Jump, what's different is the next step size k is the same with previous (not like Frog Jump problem, k-1, k and k+1). But what more complicated than Frog Jump is how to handle the duplicated elements.
Let dp[i][j] denote the number of slices ending at nums[j] with the previous nums[i],

``````[0, 1, ..., i, ..., j], [..., k]
|       |         |
pre     cur       next
``````

At j, we should check next = cur + (cur-pre) exits or not. If exists, we update

``````dp[k][j] += dp[j][i] + 1, and
result += dp[j][i] + 1;
``````
``````public int numberOfArithmeticSlices(int[] A) {
int n = A.length;
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
for(int i=0; i<n; i++){
List<Integer> list = map.get(A[i]);
if(list==null) list = new ArrayList<Integer>();
map.put(A[i], list);
}
int[][] dp = new int[n][n];
int res = 0;
for(int cur=1; cur<n; cur++){
for(int pre=cur-1; pre>=0; pre--){
long nextValue = (long)A[cur]+((long)A[cur]-A[pre]);
if(nextValue<Integer.MIN_VALUE || nextValue>Integer.MAX_VALUE) continue;
int nextVal = (int)nextValue;
if(map.containsKey(nextVal)){
List<Integer> list = map.get(nextVal);
int pos = Collections.binarySearch(list, cur+1);
pos = pos<0?(-pos-1):pos;
while(pos<list.size()){
int next = list.get(pos++);
dp[next][cur] += dp[cur][pre]+1;
res += dp[cur][pre]+1;
}

}
}
}
return res;
}
``````

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