Skip to main content

rustgym/leetcode/
_446_arithmetic_slices_2_subsequence.rs

1struct Solution;
2
3use std::collections::HashMap;
4
5impl Solution {
6    fn number_of_arithmetic_slices(a: Vec<i32>) -> i32 {
7        let n = a.len();
8        let mut dp: HashMap<(usize, i64), usize> = HashMap::new();
9        let mut res = 0;
10        for i in 0..n {
11            for j in 0..i {
12                let diff = a[i] as i64 - a[j] as i64;
13                let prev = *dp.entry((j, diff)).or_insert(1);
14                res += prev - 1;
15                *dp.entry((i, diff)).or_insert(1) += prev;
16            }
17        }
18        res as i32
19    }
20}
21
22#[test]
23fn test() {
24    let a = vec![2, 4, 6, 8, 10];
25    let res = 7;
26    assert_eq!(Solution::number_of_arithmetic_slices(a), res);
27    let a = vec![2, 2, 3, 4];
28    let res = 2;
29    assert_eq!(Solution::number_of_arithmetic_slices(a), res);
30    let a = vec![0, 2000000000, -294967296];
31    let res = 0;
32    assert_eq!(Solution::number_of_arithmetic_slices(a), res);
33}