题目描述

给你一个整数数组 nums ,返回数组 nums 中所有为等差数组的 子数组 个数。

子数组(至少有三个元素)是数组中的一个连续序列。


解题思路:

  1. dp[i]含义:以 A[i]为结尾的等差递增子区间的个数
  2. 递增子区间不一定以最后一个元素为结尾,可以是任意一个元素结尾,因此需要返回 dp 数组累加的结果。
    static int numberOfArithmeticSlices(int[] A) {
        int length = A.length;
        int[] dp = new int[length];
        if (length < 3) {
            return 0;
        }
        for (int i = 2; i < length; i++) {
            if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                dp[i] = dp[i - 1] + 1;
            }
        }
        int total = 0;
        for (int cnt : dp) {
            total += cnt;
        }
        return total;
    }

踩坑记录:

  1. dp数组定义要简介,第一次定义时直接第i个位置的等差递增子区间的个数.
  2. dp数组自底向上计算,初始值为0,每次递增1.

Q.E.D.