Given an integer array nums, return the number of arithmetic subsequences in nums.

A sequence is called an arithmetic sequence if it contains at least three elements and the difference between every pair of adjacent elements is the same.

• For example, [1, 3, 5, 7, 9], [7, 7, 7, 7], and [3, -1, -5, -9] are all arithmetic sequences.
• However, [1, 1, 2, 5, 7] is not an arithmetic sequence.

A subsequence of an array is a sequence obtained by deleting some elements from the array, possibly none.

• For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].

The input guarantees that the answer is a 32-bit integer.

Example 1:

Input:nums = [2,4,6,8,10]
Output:7
Explanation:All arithmetic subsequences 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]

Example 2:

Input:nums = [7,7,7,7,7]
Output:16
Explanation:Every subsequence of the array is an arithmetic subsequence.

Constraints:

• 1  <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1

Approach

#

This problem is almost identical to yesterday’s problem. The only difference is that a subarray has been changed to a subsequence.

However, this is a significant change: almost none of our previous reasoning is useful here.

A subsequence is not contiguous. In other words, any numbers that appear in order but are not necessarily adjacent form a valid arithmetic subsequence as long as their differences are constant.

We must understand the problem before we can solve it.

For subsequences, is there any approach other than brute force? The answer is actually simple: we only need to extract a reusable pattern.

For example, if we know that […..,2,4,6] is an arithmetic sequence, then how many elements appear before 4 is irrelevant to us. For later numbers, we do not care how many elements occur before 2, because all of them form arithmetic sequences with a difference of 2.

The outline of the data structure now emerges. The outer layer traverses the array from left to right, and at every step records information about the current element and the preceding elements for later use.

This information must be recorded based on the difference of the arithmetic sequence, so we use a HashMap<i32,?>. What should its values contain? For later use, we need to record the counts, specifically the number of valid arithmetic subsequences, but this introduces the issue of sequence length.

Length is crucial. If we record sequences of length 2, we may count too many; yet we cannot record only sequences of length at least 3, because those must be derived from sequences of length 2.

In this situation, we use a HashMap<i32, (i32, i32)>. The first i32 records sequences with length at least 3, while the second records sequences with length exactly 2.

There is another pitfall to note, which I believe many people miss:

This gives us the first version of the code:

impl Solution {
    pub fn number_of_arithmetic_slices(nums: Vec<i32>) -> i32 {
        use std::collections::*;
        let mut dp: Vec<HashMap<i64, (i32, i32)>> = vec![];
        let n = nums.len();
        let mut res = 0;
        for i in 0..n {
            let mut nxt = HashMap::new();
            for j in 0..i {
                let diff = nums[i] as i64 - nums[j] as i64;
                if let Some(value) = dp[j].get(&diff) {
                    nxt.entry(diff).or_insert((0, 0)).0 += value.0 + value.1;
                    res += value.0 + value.1;
                }
                nxt.entry(diff).or_insert((0, 0)).1 += 1;
            }
            dp.push(nxt);
        }
        res
    }
}

dp is the aggregate of all information for every position. We record all data while traversing nums.

nxt.entry(diff).or_insert((0, 0)).1 += 1; This means that every nums[j] before position i can form a length-2 combination with nums[i], so it is added to the later position.

nxt.entry(diff).or_insert((0, 0)).0 += value.0 + value.1; This means that if a sequence of length greater than 3 or exactly 2 has appeared before position j, combining it with nums[i] necessarily produces a subsequence of length at least 3. We add it to the preceding position and to the answer.

This code passes, but notice one key point. When using (i32, i32), we always use their sum. The only expression that appears in the code is value[0] + value[1]. Can we merge the two values?

Yes. After merging them, HashMap<i64, i32> represents the number of all subsequences of length at least 2 for a particular diff. Surprisingly, this does not affect the calculation.

Rust Code

#

impl Solution {
    pub fn number_of_arithmetic_slices(nums: Vec<i32>) -> i32 {
        use std::collections::*;
        let mut dp: Vec<HashMap<i64, i32>> = vec![];
        let n = nums.len();
        let mut res = 0;
        for i in 0..n {
            let mut nxt = HashMap::new();
            for j in 0..i {
                let diff = nums[i] as i64 - nums[j] as i64;
                if let Some(value) = dp[j].get(&diff) {
                    *nxt.entry(diff).or_insert(0) += value;
                    res += value;
                }
                *nxt.entry(diff).or_insert(0) += 1;
            }
            dp.push(nxt);
        }
        res
    }
}

Do you see it? The answer is obtained by adding the length-2 subsequences from the previous position; after adding the current element, they necessarily become sequences of length at least 3, so our concern was unnecessary! 😂