网站建设中目录是什么意思,做er图的网站,做网站除了有服务器还需要什么,创意网站设计团队413. 等差数列划分 - 力扣#xff08;LeetCode#xff09;
题目要求#xff1a;
如果一个数列 至少有三个元素 #xff0c;并且任意两个相邻元素之差相同#xff0c;则称该数列为等差数列。
例如#xff0c;[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
给…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-2n-3......1个f[i-1]记录的长度进行计算长度小于3不计算即可。然后nums[i]与nums[i-1]必然构成一个长度为2的等差数列所以f[i]赋值为2即可。 最后对于如果最后一个元素也属于一个等差数列此时已经跳出循环最后一个等差数列就不会结算了所以循环结束后再对等差数列进行结算。
class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {int n nums.size();if (n 3)return 0;vectorint 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(vectorint 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;}
};
