每日一练：等差数列划分

413. 等差数列划分 - 力扣（LeetCode）

题目要求：

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

• 例如，[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 动态规划 O(N)：

        首先我们假设两个数字也能构成等差数列，那么任意两个数字都能构成一个长度为2的等差数列。

        创建一个dp表，存放以 i 为结尾的最长等差数列的长度，只要nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]；那么当前的nums[i]就会和前面的等差数列也构成等差数列，那么等差数列长度+1，即：

                                                                f[i] = f[i - 1] + 1;

        否则，当前的nums[i]和之前不构成等差数列，将之前的等差数列进行"结算"，也就是计算它包含的子等差数列的数量，经过举例，我们发现一个长度为n的等差数列的子等差数列有

n-2+n-3+......+1个，f[i-1]记录的长度进行计算，长度小于3不计算即可。然后nums[i]与nums[i-1]必然构成一个长度为2的等差数列，所以f[i]赋值为2即可。

        最后，对于如果最后一个元素也属于一个等差数列，此时已经跳出循环，最后一个等差数列就不会"结算"了，所以循环结束后再对等差数列进行"结算"。

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n = nums.size();if (n < 3)return 0;vector<int> f(n); // 以i为结尾的最长等差数列长度f[1] = 2;int ret = 0;for (int i = 2; i < n; i++) {if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {f[i] = f[i - 1] + 1;} else {for (int j = f[i - 1] - 2; j >= 1; j--) // 结算ret += j;f[i] = 2;}}for (int i = f[n - 1] - 2; i >= 1; i--) // 结算ret += i;return ret;}
};

        优化-滑动窗口：

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