ArithmeticSlices.cpp

//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.

#include<vector>
#include<algorithm>

using namespace std;

class ArithmeticSlices {
public:
	int numberOfArithmeticSlices(vector<int>& a) {
		int i = 0, n = a.size();
		int res = 0;
		while (i<n - 2){
			while (i<n - 2 && a[i + 1] - a[i] != a[i + 2] - a[i + 1]) ++i;
			int start = i;
			int d = a[start + 1] - a[start];
			while (i<n - 1 && a[i + 1] - a[i] == d) ++i;
			res += (i - start)*(i - start - 1) / 2;
		}
		return res;
	}
};