江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第413题：等差数列划分

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。 - 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。 给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。 子数组 是数组中的一个连续序列。

📖 文章摘要

本文详细解析LeetCode第413题“等差数列划分”，这是一道考察数组和动态规划的题目。文章提供了多种解法，包含C#、Python、C++三种语言实现，配有详细的分析和性能对比。适合中等水平的算法学习者。

核心知识点： 动态规划、等差数列、数组处理
难度等级： 中等
推荐人群： 算法进阶学习者、面试准备者

题目描述

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

  • 例如，[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

解题思路

方法一：动态规划

使用动态规划来解决这个问题，通过记录以每个位置结尾的等差数列个数。

关键点：

  1. 判断相邻三个数是否构成等差数列
  2. 利用前一个位置的等差数列个数
  3. 累加所有位置的等差数列个数

具体步骤：

  1. 初始化dp数组，记录以每个位置结尾的等差数列个数
  2. 遍历数组，判断每个位置是否可以构成新的等差数列
  3. 如果可以构成等差数列，则dp[i] = dp[i-1] + 1
  4. 累加所有dp值得到结果

方法二：滑动窗口

使用滑动窗口来寻找连续的等差数列。

关键点：

  1. 维护一个窗口，保证窗口内的数构成等差数列
  2. 计算每个等差数列可以贡献的子数组个数
  3. 处理窗口的扩展和收缩

图解思路

算法步骤分析表

步骤 操作 状态 说明
初始状态 - dp=[0,0,0,0] 初始化dp数组
检查[1,2,3] 计算差值 dp=[0,0,1,0] 找到第一个等差数列
检查[2,3,4] 计算差值 dp=[0,0,1,2] 找到第二个等差数列
计算总和 累加dp值 result=3 得到最终结果

状态/情况分析表

情况 输入 输出 说明
基本情况 [1,2,3,4] 3 包含多个等差数列
单个元素 [1] 0 不构成等差数列
等差数列 [1,3,5,7] 3 公差为2的等差数列
非等差 [1,2,4,6] 0 不构成等差数列

代码实现

C# 实现

public class Solution {
    public int NumberOfArithmeticSlices(int[] nums) {
        int n = nums.Length;
        if (n < 3) return 0;
        
        int[] dp = new int[n];
        int result = 0;
        
        for (int i = 2; i < n; i++) {
            if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
                dp[i] = dp[i-1] + 1;
                result += dp[i];
            }
        }
        
        return result;
    }
}

Python 实现

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return 0
            
        dp = [0] * n
        result = 0
        
        for i in range(2, n):
            if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
                dp[i] = dp[i-1] + 1
                result += dp[i]
                
        return result

C++ 实现

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return 0;
        
        vector<int> dp(n);
        int result = 0;
        
        for (int i = 2; i < n; i++) {
            if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
                dp[i] = dp[i-1] + 1;
                result += dp[i];
            }
        }
        
        return result;
    }
};

执行结果

C# 实现

  • 执行用时：84 ms
  • 内存消耗：38.2 MB

Python 实现

  • 执行用时：36 ms
  • 内存消耗：15.1 MB

C++ 实现

  • 执行用时：0 ms
  • 内存消耗：7.3 MB

性能对比

语言 执行用时 内存消耗 特点
C++ 0 ms 7.3 MB 性能最优，内存占用最小
Python 36 ms 15.1 MB 代码简洁，性能适中
C# 84 ms 38.2 MB 实现清晰，内存占用较大

代码亮点

  1. 🎯 使用动态规划优化时间复杂度
  2. 💡 巧妙利用等差数列的性质
  3. 🔍 空间复杂度优化的可能性
  4. 🎨 代码结构清晰，变量命名规范

常见错误分析

  1. 🚫 未考虑数组长度小于3的情况
  2. 🚫 错误计算等差数列的个数
  3. 🚫 未正确处理动态规划状态转移
  4. 🚫 忽略了连续性要求

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
动态规划 O(n) O(n) 思路清晰 需要额外空间
滑动窗口 O(n) O(1) 空间效率高 实现复杂

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第413题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！