具体思想:
双指针可以做,而且还挺快;
但是官方想用的方法是差分数组,这个属实是没想到,给忘了;
这里有一个小技巧;
自己计数是算最大距离阶乘的,但是其实可以不用这样算;
直接新开计数,3位+1,4位+2,。。。以此类推;
变相计算了阶乘;
具体代码:
双指针:
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
if(nums.size()<3){
return 0;
}
int l=0,r=2;
int div=nums[1]-nums[0];
int cnt=0;
while(r<nums.size()){
if(nums[r]-nums[r-1]!=div){
if(r-l>=3){
cnt+=cal(r-l-3+1);
}
l=r-1;
if(r+1>nums.size())
return cnt;
div=nums[l+1]-nums[l];
r+=1;
continue;
}
r++;
if(r==nums.size()){
if(r-l>=3){
cnt+=cal(r-l-3+1);
}
}
}
return cnt;
}
int cal(int n){
int ret=0;
while(n!=0){
ret+=n;
n--;
}
return ret;
}
};
差分数组:
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
if(nums.size()<3)
return 0;
int d=nums[1]-nums[0];
int ret=0;
int t=0;
for(int i=2;i<nums.size();i++){
if(nums[i]-nums[i-1]==d){
t++;
}else{
t=0;
d=nums[i]-nums[i-1];
}
ret+=t;
}
return ret;
}
};
版权声明:本文为m0_66776925原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。