LeetCode问题的递归实现

Question

问题名：413。算术切片

问题陈述：

如果一个数字序列至少由三个元素组成，并且任意两个连续元素之间的差异相同，则称为算术序列。

例如，这些是算术序列：

1、3、5、7、9

7，7，7，7

3，-1，-5，-9

下面的序列不是算术序列。

1，1，2，5，7

给出了一个由N个数组成的零索引阵列A.该数组的一个切片是任意一对整数(P，Q)，使得0 <= P

如果序列为AP，Ap + 1，…，AQ-1，AQ为算术，则称为A阵列的片(P，Q)。这尤其意味着P+1< Q。

函数应该返回数组A中的算术片数。

链接：https://leetcode.com/problems/arithmetic-slices/

我试图找出解决上述问题的递归算法。我试图实现的算法基本上是取数组的一部分，然后递归地解决这个问题，直到数组的大小达到== 3的长度为止。最后，== 3检查数组是算术的，并在此基础上返回1或0。

我的解决方案

def isArithmatic(array):
    if (array[1] - array[0]) == (array[2] - array[1]):
        return True
    return False
def arithmaticSlices(array):
    if len(array) == 3:
        if isArithmatic(array):
            return 1
        return 0
    else:    
        return arithmaticSlices(array[1:]) + arithmaticSlices(array[:len(array)-1])  

我的问题：代码返回的答案比最初的答案要小。请帮帮忙。

Answer 1

以下是LeetCode接受的一个答案。我希望简单的逻辑是有意义的：

JavaScript代码：

​

function f(A, i=2, total=0, prevSeqTotal=0){
  if (i >= A.length)
    return total

  // The number of sequences ending here is 1 (length 3)
  // plus the number ending at the previous
  // element since those all just got extended.
  if (A[i] - A[i-1] == A[i-1] - A[i-2])
    return f(A, i + 1, total + 1 + prevSeqTotal, 1 + prevSeqTotal)

  return f(A, i + 1, total, 0)
}

console.log(f([3, 1, -1, -3]))

​

Answer 2

考虑以下数组：

1, 3, 5, 7

代码计算1, 3, 5和3, 5, 7。但是，它无法计数1, 3, 5, 7 (这是长度为4的算术片)。