O(n) time, O(1) Space, no recurssion, simple buttom-up DP approach.

• Code Below Explanation.

We at least need 3 elements to start with. let's call them [a,b,c]. And let's assume it is an arithmetic. Now lets adds 1 element. If the new element also forms an arithmetic, then it adds 2 new arithmetics to the number of possible arithmetics: elements [a,b,c,d] and [b,c,d]. If we add yet another element that still forms an arithmetic with them now we have added 3 new arithmetics to total arithmetics [a,b,c,d,e], [b,c,d,e], and [c,d,e].

As a result, with addition of each new element to an arithmetic, that element is going to add N-2 new arithmetics to the previous ones, where N is the length of the current arithmetic including the new element. If the current arithmetic is broken then we have to wait until a new one is started and we can do the same with that.

The following code keeps the N-2 (length of the arithmetic minus 2) in the variable "contribution".

``````class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {

if (A.size() < 3)
return 0;

int count = 0, contribution = 0, dist = A[1] - A[0];

for (int i = 2; i < A.size(); ++i)
{
if (A[i] - A[i - 1] == dist)
{
++contribution;
count += contribution;
continue;
}

contribution = 0;
dist = A[i] - A[i - 1];
}

return count;
}
};
``````

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