**Problem:**

Please find the problem here.

**Analysis:**

It is possible for two arithmetic slices with different common difference to stick end to end, but not any closer, for example, we can have

1, 3, 5, 7, 4, 1

Therefore, we simply find the maximal length of the sequences with the same common difference, and then compute the count based on that.

**Solution:**

I claim that the consecutive sequence of $ k $ numbers with the same common difference contains $ \frac{(k - 1)(k - 2)}{2} $ arithmetic sequences. This is obviously true with $ k = 3 $. One can think of that as simply adding numbers as follow

Here is the set of all arithmetic slices with 3 numbers

1 2 3

Adding these two, here is the set of all arithmetic slices with 4 numbers. (Total 3 of them)

1 2 3 4

2 3 4

Adding these three, here is the set of all arithmetic slices with 5 numbers. (Total 6 of them)

1 2 3 4 5

2 3 4 5

3 4 5

Adding these four, here is the set of all arithmetic slices with 5 numbers. (Total 10 of them)

1 2 3 4 5 6

2 3 4 5 63 4 5 6

4 5 6

The pattern should be obvious by now.

**Code:**

#include "stdafx.h" // https://leetcode.com/problems/arithmetic-slices/ #include "LEET_ARITHMETIC_SLICES.h" #include <map> #include <iostream> #include <sstream> #include <vector> #include <string> using namespace std; namespace _LEET_ARITHMETIC_SLICES { class Solution { public: int numberOfArithmeticSlices(vector<int>& A) { if (A.size() < 2) { return 0; } int s = 0; for (size_t i = 0; i < A.size() - 2; ) { int d = A[i + 1] - A[i]; size_t j = i + 2; while (j < A.size() && A[j] - A[j - 1] == d) { j++; } int l = j - i; s += (l - 2) * (l - 1) / 2; i = j - 1; } return s; } }; }; using namespace _LEET_ARITHMETIC_SLICES; int LEET_ARITHMETIC_SLICES() { Solution solution; int case1Array[] = {1, 2, 3, 4}; vector<int> case1(case1Array, case1Array + _countof(case1Array)); cout << solution.numberOfArithmeticSlices(case1) << endl; return 0; }

## No comments :

## Post a Comment