Leetcodeプログラミング練習:Arithmetic Slices

タイトル原文:(id=413)
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.
For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.
A slice (P, Q) of array A is called arithmetic if the sequence: A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.
The function should return the number of arithmetic slices in the array A.
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.

数列を指定し、等差数列のサブ列の数を見つけます.方法は,行き先から数列を走査し,現在の要素を以前に考えた数列に加えるたびに,等差数列のサブ列がどれだけ増加したかを判断する.明らかにこれらのサブストリングは最後の要素を含むに違いない.前回の反復時の逆数2要素の差分dを記録し、現在の逆数2要素の差分が記録された数字dと同じかどうかを判断すると、増加したサブストリング数は、以前の差分dのサブストリング数にさらに1を加える.スキャン一回デジタル時間複雑度O(n)

	int numberOfArithmeticSlices(vector& A) {
		int ans1, ans2;
		ans1 = 0;
		ans2 = 0;
		int count=0, d;
		if (A.size()>1) d=A[1]-A[0];
		for (int i = 2;i < A.size();i++) {
			if (d == A[i] - A[i - 1]) {
				count = count+1;
			}
			else {
				count = 0;
				d = A[i] - A[i - 1];
			}
			if (i % 2) 
				ans1 = ans2 + count;
			else
				ans2 = ans1 + count;
		}
		return max(ans1, ans2);
	}