If a sequence has at least three elements and the difference between every pair of adjacent elements is the same, it is called an arithmetic sequence.

• For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are all arithmetic sequences.

Input:nums = [1,2,3,4]
Output:3
Explanation:There are three arithmetic subarrays in nums: [1, 2, 3], [2, 3, 4], and [1,2,3,4] itself.

Input:nums = [1]
Output:0

Approach

#

A subarray must be contiguous within the original array, so we only need to consider the differences between each pair of adjacent elements. We can preprocess these differences in a new array.

First, consider what is required to form an arithmetic sequence. The answer is exactly what the definition says: the differences must be equal. What should we do when several consecutive differences are equal?

As the examples show, when multiple consecutive differences are equal, the choices resemble a combination problem. Both [1,2,3,4] and [1,2,3], [2,3,4] are valid answers. If four consecutive numbers (that is, three consecutive gaps) have the same difference, there are three possibilities. What if there are n numbers in a row?

1.先假设存在n个可以构成等差数列的数字
例如：1,2,3,4,5,6,7,.....,n（刚好n个）
2.因为最短需要长度为3的子数组，所以长度为3的有n - 2个
3.长度为t的子数组（t<n）有n - t + 1个
4.总共有(n-2)+(n-3)+....+(1)个
还是4.所以总共有(n-2)*(n-1)/2个

However, it is difficult to determine which numbers belong to the same arithmetic sequence, and some elements may be shared across overlapping sequences. For example, in [1,2,3,2,1], the 3 can be shared by two subarrays.

We can therefore work with the gaps. First calculate the pairwise differences, or gaps, and then compare them. Transforming [1,2,3,2,1] gives [1,1,-1,-1]; whenever two consecutive gaps are equal, we know they can form a subarray. This also handles shared elements elegantly.

The approach is now clear. We only need to traverse the array once and focus on the gaps. When equal gaps occur consecutively, count them; if there are at most n consecutive gaps, add n*(n-1) to the answer.

Rust Code

#

# struct Solution;
impl Solution {
    pub fn number_of_arithmetic_slices(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut res = 0;
        let mut pre = i32::MAX;
        let mut count = 0;
        for i in 1..n {
            let item = nums[i] - nums[i - 1];
            if pre != item {
                if count > 1 {
                    res += count * (count - 1) / 2;
                }
                pre = item;
                count = 1;
            } else {
                count += 1;
            }
        }
        if count > 1 {
            res += count * (count - 1) / 2;
        }
        res
    }
}