题目描述如果一个数列 至少有三个元素 并且任意两个相邻元素之差相同则称该数列为等差数列。例如[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的等差数列。根据这个性质设anums[i−2],bnums[i−1],cnums[i]a nums[i-2],b nums[i-1],c nums[i]anums[i−2],bnums[i−1],cnums[i]当b−ac−bb-a c - bb−ac−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−ac−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初始化i0,1i 0,1i0,1时不可能有等差数列所以初始化dp[0]0dp[1]0dp[0] 0dp[1] 0dp[0]0dp[1]0返回值由于状态表示为以iii位置为结尾的子数组中等差数列的个数。所以要返回dpdpdp数组元素之和代码classSolution{public:intnumberOfArithmeticSlices(vectorintnums){intnnums.size();vectorintdp(n,0);intret0;for(inti2;in;i){intanums[i-2],bnums[i-1],cnums[i];dp[i](c-bb-a)?(dp[i-1]1):0;retdp[i];}returnret;}};
