【LeetCode】413. 等差数列划分
413. 等差数列划分（中等）
-
思路
- 由于题目求的是等差数列 ，很自然想到子数组一定满足
nums[i] - nums[i-1] == nums[i-1] -nums[i-2];。然而我们对于 dp 数组的定义通常是以 i 结尾，满足某些条件的子数组数量，而等差数组可以在任意一个位置终结，因此此题在最后需要对 dp 数组求和。
- 由于题目求的是等差数列 ，很自然想到子数组一定满足
-
代码
class Solution { public: int numberOfArithmeticSlices(vector<int>& nums) { int n = nums.size(); if(n <= 2) return 0; vector<int> dp(n, 0); for(int i=2; i<n; ++i){ if(nums[i] - nums[i-1] == nums[i-1] - nums[i-2]){ dp[i] = dp[i-1] + 1; } } return accumulate(dp.begin(), dp.end(), 0); } }; -
收获
- 题解思路很清晰，我反而把这道题想复杂了，此外，我居然还对数组进行排序，导致一开始没办法通过，稀里糊涂。