Arithmetic slices ii subsequence

Array Dynamic Programming

54.9% acceptance

Jan 13, 2026

3501

165

Given an integer array nums, return the number of all the arithmetic subsequences of nums. 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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn number_of_arithmetic_slices(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut dp: Vec<HashMap<i64, i32>> = vec![HashMap::new(); n];
    let mut result = 0;
    
    for i in 1..n {
      for j in 0..i {
        let diff = nums[i] as i64 - nums[j] as i64;
        let count_j = *dp[j].get(&diff).unwrap_or(&0);
        *dp[i].entry(diff).or_insert(0) += count_j + 1;
        result += count_j;
      }
    }
    
    result
  }
}