Java教程

413. 等差数列划分

本文主要是介绍413. 等差数列划分,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

如果一个数列 至少有三个元素 ,并且任意两个相邻元素之差相同,则称该数列为等差数列。

例如,[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
给你一个整数数组 nums ,返回数组 nums 中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列。

 

示例 1:

输入:nums = [1,2,3,4]
输出:3
解释:nums 中有三个子等差数组:[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
示例 2:

输入:nums = [1]
输出:0
 

提示:

1 <= nums.length <= 5000
-1000 <= nums[i] <= 1000

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        if not nums: return 0

        res = []
        count = 0
        diff = None
        for i in range(len(nums) - 1):
            cur_diff = nums[i + 1] - nums[i]
            if cur_diff != diff:
                if count >= 3:
                    if cur_diff == 0:
                        res.append(1)
                    else:
                        res.append(count - 2)

                count = 1
                diff = cur_diff
            else:
                if i == len(nums) - 2:
                    res.append(count - 1)
                    break

            count += 1

        # 计算总数
        sum = 0
        for num in res:
            sum += self.help(num)

        return sum

    # 计算子数组个数
    def help(self, num):
        n = num
        s = n * 1 + n * (n - 1) // 2
        return s

 

这篇关于413. 等差数列划分的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!