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。我如何修复我的代码以获得来自整个数组[1,2,3,4]的算术切片？

Answer 1

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

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

2. 您必须检查它们是否是算术切片。

一个可以理解的解决方案，它不具有内存和时间效率，如下所示：

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