Python O(n) one pass


  • 0
    F
    class Solution(object):
        def numberOfArithmeticSlices(self, A):
            """
            :type A: List[int]
            :rtype: int
            """
            if len(A) < 3:
                return 0 
            result = 0 
            start = 0
            diff = A[1] - A[0]
            j = 2 
            while j < len(A):
                if A[j]-A[j-1]!=diff:
                    l = j - start
                    result = result + l*(l-2) - (l-2)*(l+1)/2 
                    diff = A[j] - A[j-1]
                    start = j-1 
                j = j + 1 
            l = j - start
            result = result + l*(l-2) - (l-2)*(l+1)/2   
            return result 
            
    

Log in to reply
 

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