Given an integer array nums, return the number of all the arithmetic subsequences ofnums.
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, [1, 3, 5, 7, 9], [7, 7, 7, 7], and [3, -1, -5, -9] are arithmetic sequences.
For example, [1, 1, 2, 5, 7] is not an arithmetic sequence.
A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.
For example, [2,5,10] is a subsequence of [1,2,1,**2**,4,1,**5**,**10**].
The test cases are generated so that the answer fits in 32-bit integer.
To count all arithmetic subsequences (length ≥ 3), we can use dynamic programming. For each pair of indices (j, i), if nums[i] - nums[j] = d, then any arithmetic subsequence ending at j with difference d can be extended by nums[i].
We use an array of hash maps, where f[i][d] is the number of arithmetic subsequences ending at index i with difference d (including pairs, i.e., length 2). We only count those of length ≥ 3 in the answer.
from collections import defaultdict
from typing import List
classSolution:
defnumberOfArithmeticSlices(self, nums: List[int]) -> int:
f = [defaultdict(int) for _ in nums]
ans =0for i, x in enumerate(nums):
for j, y in enumerate(nums[:i]):
d = x - y
ans += f[j][d]
f[i][d] += f[j][d] +1return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;
classSolution {
publicintnumberOfArithmeticSlices(int[] nums) {
int n = nums.length;
Map<Long, Integer>[] f =new Map[n];
Arrays.setAll(f, k ->new HashMap<>());
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
long d = 1L * nums[i]- nums[j];
int cnt = f[j].getOrDefault(d, 0);
ans += cnt;
f[i].put(d, f[i].getOrDefault(d, 0) + cnt + 1);
}
}
return ans;
}
}