LeetCode 413. 等差数列划分

Categories:

题目描述
思路分析
1. 解法一：线性 DP 计数（推荐）
相似题目

题目描述

✅ 413. 等差数列划分

思路分析

解法一：线性 DP 计数（推荐）

核心思路：

若 nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，则以 i 结尾的等差片段数量为 dp[i] = dp[i-1] + 1。

否则 dp[i] = 0。

累加所有 dp[i] 即为答案。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)。

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums.length < 3) {
            return 0;
        }

        int total = 0;
        int cur = 0;

        for (int i = 2; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                cur++;
                total += cur;
            } else {
                cur = 0;
            }
        }

        return total;
    }
}

func numberOfArithmeticSlices(nums []int) int {
	if len(nums) < 3 {
		return 0
	}

	total := 0
	cur := 0

	for i := 2; i < len(nums); i++ {
		if nums[i]-nums[i-1] == nums[i-1]-nums[i-2] {
			cur++
			total += cur
		} else {
			cur = 0
		}
	}

	return total
}

相似题目

题目	难度	考察点
446. 等差数列划分 II - 子序列	困难	DP
1027. 最长等差数列	中等	DP
1218. 最长定差子序列	中等	DP
1502. 判断能否形成等差数列	简单	排序
1784. 检查二进制字符串字段	简单	遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/81248279