## Thursday, October 27, 2016

### LeetCode OJ - Arithmetic Slices

Problem:

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 6
3 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;
}