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