No.413 等差数列划分

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

• 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

输入：nums = [1]
输出：0

思路分析

子数组一定是在原数组中连续的，所以我们关心的只有原数组中的两两之差。所以可以预处理一下，开一个新的数组存相邻数字的差。
先来思考一个问题，什么样的才能构成等差数列。
答案：字面意思，差相等。那么如果出现连读多个差相等的情况该怎么办呢

根据示例可见，如果出现多个连续的差相等的情况，其实是比较类似排列组合的一个选择，比如[1,2,3,4]和[1,2,3]、[2,3,4]都是合法答案。 如果连续四个数（也就是连续三个缝隙）差相等，就存在三种情况。如果连续n个数字呢？

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个

但对于我们来说，计算哪几个数在同一个等差数列很困难，而且存在交叉公用的情况，比如[1,2,3,2,1]中的3，就可能是两个子数组公用的数。
所以我们用缝隙来处理，先计算出两两之差（即缝隙），再比较。
将[1,2,3,2,1]处理成[1,1,-1,-1]这样，只要出现两个连续的缝隙，我们就认为可以组成子数组。
这样也很巧妙地处理了公用数字的情况。

那么思路就非常清晰了，我们只需要遍历一遍数组，只关心缝隙，在缝隙连续出现的时候统计，最多连续出现n个缝隙，然后再将答案加上n*(n-1)即可

Rust代码

#![allow(unused)]
fn main() {
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
    }
}
}