public int numberOfArithmeticSlices(int[] A) {
int re = 0;
HashMap<Integer, Integer>[] maps = new HashMap[A.length];
for(int i=0; i<A.length; i++) {
maps[i] = new HashMap<>();
int num = A[i];
for(int j=0; j<i; j++) {
if((long)numA[j]>Integer.MAX_VALUE) continue;
if((long)numA[j]<Integer.MIN_VALUE) continue;
int diff = num  A[j];
int count = maps[j].getOrDefault(diff, 0);
maps[i].put(diff, maps[i].getOrDefault(diff,0)+count+1);
re += count;
}
}
return re;
}
JAVA 15 lines solution


@haili2
I think the idea is based on each element to cal the number of all possible differences cases.
[2,4,6,8,10]
Like based on 6, to calculate the difference value of 4,2,0,2,4, the map is
4:1
2:2
so when we move to element 8, the map will be
6:1
4:1
2:3

correct me if I'm wrong.
I think the idea is to store the diff and number of times this diff has appeared before in a hash map for each element;
And we only calculate the diff between current element and the element before current.
for example:
[2] stores a empty hashmap
[2,4] now 4 stores a mapentry [2,1] because 42 = 2,and for element 2 stores nothing
[2,4,6] 64 =2 and since element 4 stores[2,1], which means diff 2 has appeared once before, so count = 1 and we put [2,2] in 6. Also 62 = 4, we put [4,1] in 6;the timing of record count and pass it to the result is perfect, i wish i could work it out by myself one day
hope it helps!

Try to make a explanation:
Given a array
[1,2,2,3,4]
, we want to find the number of all the unique subsequences (with at least three element) with same difference between two consecutive number in the subsequence. If we know the number of unique subsequences of array[1,2,2,3]
, we can find the answer to the array[1,2,2,3,4]
just by finding all the valid sequences ends in number4
. This brings us the idea that this is DP Problem. So we build our answer by searching for all valid subsequence ending with each number in the array.But how can we find all the valid subsequences ending in number
4
for example. We search for the number that comes before4
, so we do iterate through all the numberpreNum
before4
, take the differencediff = 4  preNum
. Then we see if we can know all the valid subsequences ending inpreNum
with differencediff
, we say we find all the valid subsequences ending in4
with differencediff
. To maintain that information, we useHashMap
for each element in the array. The keyvalue will be<diff, len>
means the longest valid subsequence ending in this number with consecutive differencediff
has lengthlen
.Then we traverse through all the element in the array, for all the
diff
, add up the number of valid subsequence, we should get the answer. But there are edge cases that should be handled with care.For the Example
[1,2,2,3,4]
. We see there are duplicate numbers and we may overwrite what we have and leave some valid answer. The map building is like[ 1, 2 , 2, 3, 4] <1, 1> <0, 1> <1, 4> <1,5> <1,1> <2, 1> <2,1> <3,1>
cause we have two
2
before number3
, we have to add up the previous value if themap
already have thediff
key.