Day.23

leetcode 413.等差数列划分

问题：如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。给你一个整数数组 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. 边界：

   int n = nums.size();
   if (n < 3)
       return 0;
   

   • 首先获取数组的长度 n。
   • 如果数组长度小于 3，直接返回 0。

2. 初始化变量：

   int count = 0, dp = 0;
   

   • count：记录总的等差数列子数组的个数。
   • dp：记录当前连续的等差数列子数组的个数。

3. 遍历数组：

   for (int i = 2; i < n; i++) {
       if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
           dp += 1;
           count += dp;
       } else {
           dp = 0;
       }
   }
   

   • 从第三个元素开始遍历。

   • 检查当前元素 nums[i]、前一个元素 nums[i-1] 和前前一个元素 nums[i-2] 是否构成等差数列：

     • 如果满足，则dp += 1，当前连续的等差数列子数组长度增加1，

     count += dp，再将当前的等差数列子数组个数累加到 count 中。

     • 如果不满足，则重置当前连续的等差数列子数组个数为0。

4. 返回结果：

return count;

代码：

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