如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
- 例如，
[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
题解
8月10日每日一题
这题比较简单，题目中已经说明了，给出的int[] nums必定是符合条件的分段等差数列，所以，我们其实要做的就是找出各个分段之间的界限，分别求出各个分段的子序列数量并求和。
那么。如果想要在一次遍历中完成这样的操作，我们需要记录几个关键的信息
- 当前位置和上一个位置的数字的差值（i位置和i-1位置的差值）
- 上一个位置和上上一个的差值（i-1和i-2位置）
- 如果这两个值相等则表示当前数字仍然在同一个等差区间之中，如果不等，则表示已经进入了一个新的等差区间
- 还有一个重要的信息，就是当前等差区间的开始位置
接下来分情况讨论。
- 如果不等于：表明当前位置是处于两个不同等差分段相接的部分。需要更新差值信息和分段起始位置。
按照逻辑来说，当前位置应当是分段起始位置。比如[1,2,3,8,9,10]的数组，当我们到达数字8的索引3的时候，知道了起始位置为3。8和前面的值3的差值为5，而当我们到达数字9的时候，9和8的差值为1，是不是应该重新记录分段开始位置呢？显然是错误的，本题中要求子序列最短长度为3，所以只有到达9的时候我们才会知道分段起始位置应该为8所在的位置。
如果9后面的值不是10，那么分段起始位置会重新刷新，如果是10，那么满足了上面的i – （i-1） 等于 （i-1）-（i-2）位置的值，则恰好分段开始位置为8所在的位置。
- 如果是值等于的情况
本来写了长度判断，但是再看了下，能进入这个条件的，必定是长度至少为3的等差分段区间。然后求出当前区间的子序列个数最终求和。
我们来看下，设等差区间的长度为k
当k=3的时候，子序列个数为1
当k=4的时候，子序列个数为1（自身4个）+2（长度为3的2个子序列）
当k=5的时候，子序列个数为1（自身5个）+2（长度为4的2个子序列）+3（长度为3的3个子序列）
当k=6的时候，子序列个数为1（自身6个）+2（长度为5的2个子序列）+3（长度为4的3个子序列）+4（长度为3的4个子序列）
所以，其实很明白了，就是从1开始到指定数字的求和公式n(n+1)/2
但是这边的合是一次性的，而我们的计算是遍历中求的，不可能当我们还在i点的时候就知道有当前等差分段区间终止位置为i+i’位置，（当然也可以选择在找到3个连续的等差数字的之后往后探测找到结尾位置）。所以我们在遍历中需要在n位置得到总数后，再减去前面一次多加了的，即（n(n+1)/2）-（n(n-1)/2）= n。
这样就很简单明了了，当差区间的长度k=3的时候只需总数+1，k=4的时候只需总数再加2，k=5的之后总数再加3，以此类推。
代码：
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
if (nums.length<3){
return 0;
}
int dis = 0;
int sum = 0;
int lastDis = nums[1]-nums[0];
int disIndexStart = 0;
for (int i = 2; i < nums.length; i++) {
dis = nums[i]-nums[i-1];
if (dis != lastDis){
lastDis = dis;
disIndexStart = i-1;
continue;
}else{
//if (i-disIndexStart >= 2){
//超过三个了
sum+=i-disIndexStart-1;
//}
}
}
return sum;
}
}
//leetcode submit region end(Prohibit modification and deletion)解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:36 MB,击败了87.74% 的Java用户
发表评论