思路:dp
因为正在练dp,所以这里就用dp的方法做了。
通过我们做过的一个题,就是leetcode 53.最大子段和那个,还有最长递增序列那一类题,我们可以知道,设置dp含义一般都是以什么什么数结尾,然后再去写转移方程。
这里还是一样,把nums[i]为尾作为dp数组的含义。
然后,我们想,这里不一样的地方其实还是在于长度必须是严格大于等于3这个条件,所以在这之前我们的dp数组都应该是0才对,从i=2这个下标才真正开始计数。
这里作者一开始在想和子段和有何不同的时候,没有想到价值怎么加,后来才发现这个只是对于个数计数,价值是1才对。
也就是说,当nums[i]-nums[i-1]==nums[i-1]-nums[i-2]的时候,我们这个时候默认是有三个数在一块并且是等差的,这个时候是符合条件的。dp[i]=dp[i-1]+1
上代码:
class Solution {public int numberOfArithmeticSlices(int[] nums) {int n=nums.length;if(n<3)return 0;int []num=new int[n];for(int i=2;i<n;i++){if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]){num[i]=num[i-1]+1;}}int ans=0;for(int i=2;i<n;i++){ans+=num[i];}return ans;}
}