Python O(n) time O(1) space solution using DP, easy to understand


  • 2
    G

    As we go through the array, if the current element forms Arithmetic Slices with previous elements A[i] - A[i - 1] == A[i - 1] - A[i - 2], we can add last_slice_length - 1 more slices to the result, other wise assign last_slice_length = 2. Try simple case 123456, you will understand.

    class Solution(object):
        def numberOfArithmeticSlices(self, A):
            """
            :type A: List[int]
            :rtype: int
            """
            dp = 0
            last_slice_length = 1
            for i in range(1, len(A)):
                if last_slice_length >= 2 and A[i] - A[i - 1] == A[i - 1] - A[i - 2]:
                    dp = last_slice_length - 1 + dp
                    last_slice_length = last_slice_length + 1
                else:
                    last_slice_length = 2
            return dp
    

Log in to reply
 

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