413. 等差数列划分

一、413. 等差数列划分 1.1、题目描述

1.2.1、直接暴力法

class Solution:
    def numberOfArithmeticSlices(self, A: List[int]) -> int:
        count = 0

        n = len(A)
        for i in range(n-2):
            d = A[i] - A[i+1]
            for j in range(i+2, n): 
                if d == A[j-1] - A[j]: 
                    count += 1
                else:   # 一旦出现不满足，就不需要判断
                    break
        return count

1.2.2、递归

class Solution:
    def __init__(self):
        self.count = 0
    
    def numberOfArithmeticSlices(self, A: List[int]) -> int:
        self.slicens(A, len(A)-1)
        return self.count
        
    def slicens(self, A: List[int], i: int) -> int:
        if i  int:
        n = len(A)
        if n  int:
        n = len(A)
        if n  int:
        n = len(A)
        ans = 0

        count = 0
        # 
        for i in range(2, n):
            if A[i] - A[i-1] == A[i-1] - A[i-2]:
               count += 1
            else: 不满足， 前面有多个连续序列
                ans += count * (count + 1) // 2
                count = 0
        return  ans + count * (count + 1) // 2