Question

Given an unsorted array of length N, a slice is defined as a pair of numbers (P, Q) so that:

  1. 0 <= P < Q <= N
  2. A[P], A[P+1]….A[Q] is arithmetic sequence

Example: 

input = { -1, 1, 3, 3, 3, 2, 1, 0 }

Output 5 because there’re slices: 

(0, 2) (2, 4) (4, 6) (4, 7) (5, 7)

Solution

  1. count the length of arithmetic (countinuous) sequence
  2. form some slices
  3. proceed from the end of that sequence, till the end.

Code

public int solve(int[] input) {
	int len = input.length;
	int p = 0;
	int totalSlices = 0;

	while (p + 1 < len) {
		// check if there is a arithmetic sequence starting at p
		// note that p is NOT the last element.
		int diff = input[p + 1] - input[p];
		int q = p + 1;

		// starting from q, check arithmetic difference
		while (q < len) {
			if (input[q] - input[q - 1] == diff) {
				q++;
			} else {
				break;
			}
		}

		// so, the range [p, q-1] is a arithmetic sequence.
		int seqLength = q - p;
		if (seqLength >= 3) {
			totalSlices += getSlicesCountFromArithmeticSeq(seqLength);
		}

		// update p (skip the range [p, q-1])
		p = q - 1;
	}
	return totalSlices;
}

private int getSlicesCountFromArithmeticSeq(int k) {
	// choose 2 from (k - 1)
	return (k - 1) * (k - 2) / 2;
}