# 446. Arithmetic Slices II - Subsequence

A sequence of numbers 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 sequences:

``````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 subsequence slice of that array is any sequence of integers (P0, P1, …, Pk) such that 0 ≤ P0 < P1 < … < Pk < N.

A subsequence slice (P0, P1, …, Pk) of array A is called arithmetic if the sequence A[P0], A[P1], …, A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.

The function should return the number of arithmetic subsequence slices in the array A.

The input contains N integers. Every integer is in the range of -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1.

Example:

``````Input: [2, 4, 6, 8, 10]

Output: 7

Explanation:
All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
``````

``````2     4     6     8     10
2->1  4->1  6->1  8->1
2->2  4->1  6->1
2->3  4->2
2->4
``````

2->2：[2,4,6]

2->3：[2,4,6,8]    [4,6,8]

4->2：[2,6,10]

2->4：[2,4,6,8,10]    [4,6,8,10]    [6,8,10]

``````class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int res = 0, n = A.size();
vector<unordered_map<int, int>> dp(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
long delta = (long)A[i] - A[j];
if (delta > INT_MAX || delta < INT_MIN) continue;
int diff = (int)delta;
++dp[i][diff];
if (dp[j].count(diff)) {
res += dp[j][diff];
dp[i][diff] += dp[j][diff];
}
}
}
return res;
}
};
``````

Arithmetic Slices

https://leetcode.com/problems/arithmetic-slices-ii-subsequence/solution/

https://leetcode.com/problems/arithmetic-slices-ii-subsequence/discuss/92837/C++_DP_Accepted

https://leetcode.com/problems/arithmetic-slices-ii-subsequence/discuss/92822/Detailed-explanation-for-Java-O(n2)-solution

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation