[LeetCode]Arithmetic Slices

用DP[i]表示在i位置结尾的AS(arithmetic slice)，那么我们有递推公式：

• if nums[i] - nums[i - 1] != nums[i - 1] - nums[i - 2], DP[i] = 0
• else, DP[i] = DP[i - 1] + 1(DP[i - 1]的所有AS在i处结尾都仍然是AS，同时多出一个在i处结尾的长度为3的AS)

可以优化成常数空间，时间复杂度O(n)，代码如下：

	class Solution {
	public:
	int numberOfArithmeticSlices(vector<int>& A) {
	int len = A.size(), res = 0, currNum = 0, i = 2;
	while(i < len)
	{
	if(A[i] - A[i - 1] == A[i - 1] - A[i - 2])
	++currNum;
	else
	currNum = 0;
	res += currNum;
	++i;
	}
	return res;
	}
	};

view raw Arithmetic Slices_2.cpp hosted with ❤ by GitHub

同时我们可以观察到，如果我们找到一个等差区间，有k个数(k >= 3)，那么我们可以增加(k - 2) * (k - 1) / 2个AS，那么我们可以得到另外一种写法，代码如下：

	class Solution {
	public:
	int numberOfArithmeticSlices(vector<int>& A) {
	int len = A.size(), res = 0, currNum = 0, i = 2;
	while(i < len)
	{
	if(A[i] - A[i - 1] == A[i - 1] - A[i - 2])
	++currNum;
	else
	currNum = 0;
	res += currNum;
	++i;
	}
	return res;
	}
	};

view raw Arithmetic Slices_2.cpp hosted with ❤ by GitHub