【算法|动态规划No.19】leetcode413. 等差数列划分

妖狐艹你老母 2024-04-27 06:35 71阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[手撕算法系列专栏][Link 2]】【[LeetCode][]】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?希望我们一起努力、成长，共同进步。  
> ![在这里插入图片描述][530b2fdc59bf45d5bfa43fd373793841.png]

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣题目解析
 *  3️⃣解题代码

## 1️⃣题目描述 ##

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

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

## 2️⃣题目解析 ##

**解题思路如下：**

*  `整个程序从第三个元素开始遍历序列。对于每一个位置i，首先判断前两个元素nums[i-2]、nums[i-1]和当前元素nums[i]是否构成等差数列。如果构成等差数列，那么dp[i]的值就可以通过dp[i-1] + 1计算得到。其中dp[i-1]表示以前一个元素为结尾的等差数列的个数，而加上当前元素后形成了以当前元素为结尾的新的等差数列。如果不构成等差数列，那么dp[i]的值就设为0，代表不以当前元素为结尾的等差数列个数为0。`

## 3️⃣解题代码 ##

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

**最后就通过啦！！！**

![在这里插入图片描述][3bc9c8f18c3f4a4ab67875a0cd76b124.png]

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[LeetCode]: https://blog.csdn.net/m0_74352571/category_12252087.html
[530b2fdc59bf45d5bfa43fd373793841.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/828a727fcb3b41119e5dc103a3e2e1ff.png
[3bc9c8f18c3f4a4ab67875a0cd76b124.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/78a0a15ad758457280e98ee493f517f0.png