Click here to see the full article post
Hi @kevinkeya, #5 is DP with an array and without an array to track the previously calculated slice counts. Without the array uses less memory, but this is not a significant enough change to warrant another approach number I suppose.
def numberOfArithmeticSlices(self, A): """ :type A: List[int] :rtype: int """ p = 0 q = 2 lengthS = 0#length of arithmetic segment count = 0 while q < len(A): diff1 = A[q] - A[p +1] diff2 = A[p+1] - A[p] prevQ = A[q-1] if diff2 == diff1 : #if arithmetic, find whole arithmetic segment while(q < len(A) and diff1 == (A[q] - prevQ)):#while still arithmetic prevQ = A[q] q+=1 lengthS = q - p for i in range(1, lengthS - 1): count += i p = q else:#segment of 3 was not arithmetic, check next segment of 3 p+=1 q = p + 2 return count
My solution uses a window to scan 3 elements of the array. If these 3 are 'arithmetic', increase upper bound of this window to find all elements considered to be arithmetic together. If the next element breaks the chain, update p = q and restart scanning with the 3 element window.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.