Leetcode 446. Arithmetic Slices II - Subsequence

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

题意:求一个数组中能够组成等差数列的的组合的个数

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 res = 0, size = A.size();
vector<unordered_map<int, int> > dp(size);
for(int i = 0; i < size; i++){
for(int j = 0; j < i; j++){
long delta = (long) A[i] - (long) 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;
}
};
0%