image.png
image.png
解题思路：
-
dp[i]=dp[i-1]+1，由dp表示当前点i所包含的等差数列数，其状态转移方式：比前一个状态多了1，如数列1[1, 2, 3]的dp[2]值为1，而数列2在数列1的基础上加了4，[1, 2, 3, 4]的dp值因为比dp[3]=2，而数列2包含的所有子数组个数即dp值的和=3； - 假设输入数组A为长度为n的等差数列，则返回
(n-1)*(n-2)/2个子数组，因此找出A的子最大等差数列，然后分别求其子数组个数，再求和。
Python3代码
class Solution:
def numberOfArithmeticSlices(self, A: List[int]) -> int:
sum1 = 0
dp = [0 for _ in range(len(A))]
for i in range(2,len(A)):
if A[i] - A[i-1] == A[i-1]-A[i-2]:
sum1+=1
dp[i]=sum1
else:
sum1=0
dp[i]=0
return sum(dp)
Python3代码
class Solution:
def numberOfArithmeticSlices(self, A: List[int]) -> int:
r = 0
i = 0
while i < len(A)-2:
len1 = 2
while i+2<len(A) and A[i + 2] - A[i + 1] == A[i + 1] - A[i]:
len1+=1
i+=1
i+=1
r += int((len1-1)*(len1-2)/2)
return r
