Leetcode 413:算术切片Python

Question

嗨，我在试着解决Leetcode 413:算术切片。我试着从一个蛮力递归的解决方案开始。

 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)

这不适用于测试用例[1,2,3,4] (它返回2而不是3)。在我的头脑中，我知道它不起作用，因为当函数被调用时，1 + slices([1,2,3], 2)返回2。

Answer 1

为了解决这个问题，你必须采取两个步骤。

1. 首先您必须找到所有可能的连续子数组

。

1. 你必须检查它们，如果它们是算术切片。

以下是一个可以理解的、内存和时间效率低下的解决方案：

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)]

但是，一个更难掌握但内存和时间高效的解决方案如下所示(您仍然可以用循环替换递归调用，我认为这样做会得到更好的结果)：

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