413. Arithmetic Slices

  • 54.7%

https://leetcode.com/problems/arithmetic-slices/?tab=Description

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.

1
2
3
4
5
6
7
8
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.

1
2
3
4
5
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.

cpp


https://discuss.leetcode.com/topic/62992/3ms-c-standard-dp-solution-with-very-detailed-explanation

3ms C++ Standard DP Solution with Very Detailed Explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int n = A.size();
if (n < 3) return 0;
vector<int> dp(n, 0); // dp[i] means the number of arithmetic slices ending with A[i]
if (A[2]-A[1] == A[1]-A[0]) dp[2] = 1; // if the first three numbers are arithmetic or not
int result = dp[2];
for (int i = 3; i < n; ++i) {
// if A[i-2], A[i-1], A[i] are arithmetic, then the number of arithmetic slices ending with A[i] (dp[i])
// equals to:
// the number of arithmetic slices ending with A[i-1] (dp[i-1], all these arithmetic slices appending A[i] are also arithmetic)
// +
// A[i-2], A[i-1], A[i] (a brand new arithmetic slice)
// it is how dp[i] = dp[i-1] + 1 comes
if (A[i]-A[i-1] == A[i-1]-A[i-2])
dp[i] = dp[i-1] + 1;
result += dp[i]; // accumulate all valid slices
}
return result;
}
};

https://discuss.leetcode.com/topic/62162/3ms-question-maker-solution-in-cpp-o-n-time-and-in-space

3ms Question Maker Solution in CPP O(n) time and in space

I met this question in friend’s friend’s OA (recursive friend) lol

It could be solved in O(n) with small math trick~~ O(n) time and in space. Thanks @JianShi for this solution!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
if (A.size() < 3) return 0;
int size = (int) A.size();
for (int i = 0; i < size - 1; i++) {
A[i] = A[i + 1] - A[i];
}
A.resize(size - 1);
size--;

int res = 0;
int len = 1;
for (int i = 1; i < size; i++) {
if (A[i] != A[i - 1]) {
res += len * (len - 1) / 2;
len = 1;
} else {
len++;
}
}
if (len > 1) res += len * (len - 1) / 2;
return res;
}
};

https://discuss.leetcode.com/topic/62162/3ms-question-maker-solution-in-cpp-o-n-time-and-in-space/3

@codeRiya Hi, thank you for your question!

As I said, this solution uses a small math trick.

At first, it change A to an array of difference of adjacent items in original A.

For example, if A is [1,2,3,4], then A should be [1,1,1]. So for adjusted A, 2 or more continuous same values indicates there is an arithmetic slice in original A. If there is N continuous same values in adjusted A, there should be an arithmetic slice with length of N + 1.

Now let me show you how many arithmetic slices in a N + 1 long arithmetic slice.

1
2
3
4
5
6
[1,2,3] -> 1 arithmetic slice
[1,2,3,4] -> 3 arithmetic slices, 2 more than before
[1,2,3,4,5] -> 6 arithmetic slices, 3 more than before
........
Arithmetic slice with length N -> 1 + 2 + 3 + .....+ (N - 2) = (1 + N - 2) * (N - 2) / 2 = (N - 1) * (N - 2) / 2 arithmetic slice(s)
So, when length N + 1 -> (N - 1) * N / 2

If you have more question, please let me know~ cheers! :P


python


https://discuss.leetcode.com/topic/63873/python-dp-solution

Python DP solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def numberOfArithmeticSlices(self, A):
"""
:type A: List[int]
:rtype: int
"""
opt, i = [0,0], 1
for j in xrange(2,len(A)):
if A[j]-A[j-1] == A[j-1]-A[j-2]:
opt.append(opt[j-1]+i)
i += 1
else:
opt.append(opt[j-1])
i = 1
return opt[-1]

https://discuss.leetcode.com/topic/63873/python-dp-solution/2

@zhan430 Why not use a variable instead of an array?

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def numberOfArithmeticSlices(self, A):
curr, sum = 0, 0
for i in range(2,len(A)):
if A[i]-A[i-1] == A[i-1]-A[i-2]:
curr += 1
sum += curr
else:
curr = 0
return sum

java


https://discuss.leetcode.com/topic/63302/simple-java-solution-9-lines-2ms

Simple Java solution 9 lines, 2ms

1
2
3
4
5
6
7
8
9
10
11
public int numberOfArithmeticSlices(int[] A) {
int curr = 0, sum = 0;
for (int i=2; i<A.length; i++)
if (A[i]-A[i-1] == A[i-1]-A[i-2]) {
curr += 1;
sum += curr;
} else {
curr = 0;
}
return sum;
}
谢谢你,可爱的朋友。