企业官网建设流程全解析

题目描述

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

例如，[1,3,5,7,9][1,3,5,7,9][1,3,5,7,9]、[7,7,7,7][7,7,7,7][7,7,7,7]和[3,−1,−5,−9][3,-1,-5,-9][3,−1,−5,−9]都是等差数列。
给你一个整数数组numsnumsnums，返回数组numsnumsnums中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列。

示例 1：
输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

示例 2：
输入：nums = [1]
输出：0

算法原理

这是一个子数组问题，可以用动态规划解决

状态表示：子数组问题的状态表示一般是以某一个位置为结尾，这道题目也不例外。dp[i]dp[i]dp[i]表示以iii位置为结尾的子数组中，等差数列的个数

状态转移方程：先看等差数列的一个性质，假设[a,b,c,d][a,b,c,d][a,b,c,d]是公差为xxx的等差数列，[c,d,e][c,d,e][c,d,e]是一个等差数列，那么[a,b,c,d,e][a,b,c,d,e][a,b,c,d,e]也是一个公差为xxx的等差数列。根据这个性质，设a=nums[i−2],b=nums[i−1],c=nums[i]a = nums[i-2],b = nums[i-1],c = nums[i]a=nums[i−2],b=nums[i−1],c=nums[i]，

当b−a==c−bb-a == c - bb−a==c−b时，[a,b,c][a, b, c][a,b,c]是一个等差数列。如果以a,ba,ba,b为结尾的一个数组是等差数列，那以[a,b,c][a, b, c][a,b,c]为结尾的一个数组也是等差数列。以a,ba, ba,b为结尾的数组，就是以bbb结尾的数组，也就是以i−1i-1i−1位置为结尾的数组，所以
dp[i]=dp[i−1]dp[i] = dp[i-1]dp[i]=dp[i−1]由于以a,ba,ba,b为结尾的子数组还有[a,b][a, b][a,b]，它的长度是222，不会被当做等差数列，但是再加上ccc，[a,b,c][a,b,c][a,b,c]就是等差数列了，所以还要加上这个情况dp[i]=dp[i−1]+1dp[i] = dp[i - 1] + 1dp[i]=dp[i−1]+1

当b−a≠c−bb - a ≠ c - bb−a=c−b时，[a,b,c][a, b, c][a,b,c]不是一个等差数列。就算以a,ba,ba,b为结尾的所有数组都是等差数列，以[a,b,c][a, b, c][a,b,c]为结尾的所有数组也不是等差数列。所以
dp[i]=0dp[i] = 0dp[i]=0

初始化：i=0,1i = 0,1i=0,1时，不可能有等差数列，所以初始化dp[0]=0，dp[1]=0dp[0] = 0，dp[1] = 0dp[0]=0，dp[1]=0

返回值：由于状态表示为以iii位置为结尾的子数组中，等差数列的个数。所以要返回dpdpdp数组元素之和

代码

classSolution{public:intnumberOfArithmeticSlices(vector<int>&nums){intn=nums.size();vector<int>dp(n,0);intret=0;for(inti=2;i<n;++i){inta=nums[i-2],b=nums[i-1],c=nums[i];dp[i]=(c-b==b-a)?(dp[i-1]+1):0;ret+=dp[i];}returnret;}};