leetcode 413 找数组中等差数列的个数

这题是放到动态规划的题型里了。但是根本不用动态规划做。

这题的关键是：

1. 至少3个元素
2. 必须是相邻的 （这个条件让题目简单不少，如果不是连续的就比较麻烦了）

简单的思路

1. 把相邻元素的差值都求出来
2. 计算相邻元素差值相同的元素个数
3. 行数 = 相邻元素个数 + 1 - 3 ， 然后从行数 一直递减加到1
   比如5个数组成等差数列 ， 行数 = 5 - 3 + 1 = 3，
   也就是 3 + 2 + 1 = 6 种 等差数列
   具体的草稿纸写写就看出来了

package leetcode.dp;

public class _413_arslice {
    public int numberOfArithmeticSlices(int[] nums) {
        int[] diff = new int[nums.length + 1];
        for (int i = 1; i < nums.length; i++) {
             diff[i] =  nums[i] - nums[i - 1];  //diff里的值跟nums里比较大的那个数的位置对上
        }
        int len = 1;
        int sum = 0;
        for (int i = 2; i < diff.length; i++) {
            // 第二个条件是在数组结尾即使跟前面一样，也必须进行后面的求和
            if (diff[i] == diff[i -1] && i < diff.length - 1) {
                len++;
            } else {
                // len + 1 是实际数组中等差数列的长度
                // (len + 1) - 3 + 1 是等差数列中能容下长度为3的序列的长度。
                // 比如
                // nums[] = 1，3，5，7，9，10，11
                // diff[] = 0，2，2，2，2， 1， 1
                // 对应的 len + 1 就是 5， 和 2
                // row = 5 - 3 + 1 = 3， 也就是说能出现3行组合情况
                // 1，3，5，7，9可以分为
                // 3个一组  1，3，5   3，5，7   5，7，9  （3）
                // 4个一组  1，3，5，7    3，5，7，9     （2）
                // 5个一组  1，3，5，7，9               （1）
                //也就是说
                // 1，3，5，7，9的组合数是 1 + 2 + 3， 也就是(row + 1) * row / 2

                int row = len - 3 + 1 + 1;
                sum += (row + 1) * row / 2;
                len = 1;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        _413_arslice a = new _413_arslice();
        a.numberOfArithmeticSlices(new int[] {1,3,5,7,9,10,11});
    }
}