The intuitive solution is to do this in O(n^2), add one to the count of total arithmetic slices, if A[i:j] is an arithmetic slice, then we can add one, and check if A[i:j+1] is also an arithmetic slice.
Otherwise, check starting from A[i+1:] since we need to have a consecutive sequence to continue.
def numberOfArithmeticSlices(self, A): if len(A) < 3: return 0 count = 0 for i in range(len(dp)-2): for j in range(i, len(A)): if (A[j]-A[j-1]) == (A[j-1] -A[j-2]): count += 1 else: break return count
We can optimize this to O(N) by noting the fact that we only need to keep track of the previous ending, and the length of our current sequence.
[1,2,3] = 1
When we expand to 4, because [1,2,3,4] is a continuation of our last sequence of [1,2,3] we need to account for this, as well as if the arithmetic sequence were to start at 2 and be [2,3,4].
Our previous incrementer kept track of how long the last sequence was, so we just need to add one to it.
class Solution(object): def numberOfArithmeticSlices(self, A): if len(A) < 3: return 0 last_diff = A - A len_sequence = 0 count = 0 for i in range(2, len(A)): if A[i] - A[i-1] == last_diff: len_sequence +=1 count += len_sequence else: len_sequence = 0 last_diff = A[i]-A[i-1] return count