Hi I'm trying to solve Leetcode 413: Arithmetic slices. I'm trying to start with a brute force recursive solution.

 def numberOfArithmeticSlices(self, nums: List[int]) -> int:
      def slices(nums: List[int], i: int):
          if (i < 2):
              return 0
          if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
              return 1   slices(nums, i -1)
          else:
              return slices(nums, i-1)
        if len(nums) < 3:
            return 0
        return slices(nums, len(nums)-1)

This doesn't work for the test case [1,2,3,4] (it returns 2 instead of 3). In my head I know it doesn't work because when the function is called, 1 slices([1,2,3], 2) returns 2. How can I fix my code to get the arithmetic slice coming from the entire array [1,2,3,4]?

CodePudding user response：

For solving this problem you have to take two steps.

1. First you have to find all possible contiguous sub-arrays

2. You have to check them, if they are arithmetic slices.

An understandable solution which is not memory and time efficient is as below:

def numberOfArithmeticSlices(self, nums: List[int]) -> int:
    if len(nums) <= 2:
        return 0
    sub_arrays = self.contiguous_subarray(nums)  # type List[List[int]]  all contiguous sub arrays with length 3 or more
    count = 0
    for subset in sub_arrays:
        count = count   self.is_arithmetic_subset(subset)
    return count

@staticmethod
def is_arithmetic_subset(subset):
    if len(subset) <= 2:
        return 0
    diff = subset[1] - subset[0]
    for i in range(2, len(subset)):
        if subset[i] - subset[i - 1] != diff:
            return 0
    return 1

@staticmethod
def contiguous_subarray(nums):
    return [nums[i:i   j] for i in range(0, len(nums)) for j in range(3, len(nums) - i   1)]

But a solution that is little more harder to grasp but is memory and time efficient is as bellow(You could still replace the recursive call with a loop and I think you would get better results doing so):

def numberOfArithmeticSlices(self, nums: List[int]) -> int:
    array_len = len(nums)
    if array_len <= 2:
        return 0
    count = self.numberOfArithmeticSlices(nums[:array_len - 1])
    diff = nums[array_len - 1] - nums[array_len - 2]
    for i in range(2, array_len):
        if nums[array_len - i ] - nums[array_len - i - 1] == diff:
            count  = 1
        else:
            break
    return count