413. Arithmetic Slices
A sequence of number is called arithmetic if it consists of at least three elements and
if the difference between any two consecutive elements is the same.
Example:
A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
题目的意思是求一个给定数组的等差数列子集的个数。是一个动态规划的题,一开始用一个两层的循环分割数组长度,再用一个循环判断是否是等差数列,这样自然就是超时了。
用动态规划的思想,用一个数组来存储含有i的等差子集个数,如果一个等差数列,新加入的那个元素也满足和前一个数等差,那么可以得到递归公式:
最后求出数组count的和就是含有所有数字的等差子集的个数,即数组所有等差数列子集的个数。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16var numberOfArithmeticSlices = function(nums) {
let count = new Array(nums.length+1)
count.fill(0)
for(let i=2; i<nums.length; i++){
if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]){
count[i] = count[i-1] + 1
}
}
let sum = 0
for(let i=0; i<count.length; i++){
sum += count[i]
}
return sum
};