[数据结构与算法]LeetCode 413. Arithmetic Slices【数组/双指针/动态规划】中等

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，这个截止期限可能是永远。

在这一系列刷题文章中，不仅讲解多种解体思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时还会总结相应的算法模板。为了方便调试和

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

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

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

A subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

Example 2:

Input: nums = [1]
Output: 0

Constraints:

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

题意：如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

解法1 双指针

这一做法是从暴力做法中优化得到的。很容易想到，我们可以双重循环所有的子数组区间 [i, j] ，判断 nums[i], ..., nums[j] 是否是等差数列，是则计数，算法时间复杂度为 $O(n^3)$ 。不过这样做太低效了，我们可以进一步优化。

由于等差数组的子数组也是等差数组，因此在确定了起始位置 i 后，只要公差一致，指针 j 就可以向后面尽可能的扩展，从而得到以 i 为起始位置、公差 d = nums[i + 1] - nums[i] 的最长等差子数组区间 [i, j] ，令区间长度为 len = j - i + 1 ，其中符合条件的等差子数组的数量为：
$$cnt=\sum _{k=3}^{len}countArrayWithLength(k)$$

其中函数 int countArrayWithLength(int k) 求的是长度为 k 的等差子数组的数量，k 的变化区间为 [3, len] 。显然，随着 k 的增大，等差子数组的数量 cnt 逐渐减少，且实质上是一个 「首项为 1 、末项为 len - 3 + 1 、公差为 1 的等差数列的求和结果」。因此等差子数组的总数加上 cnt ，然后 i 指针跳转到 j 处，重复上述过程。

最后的代码如下：

//C++ version
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        if (nums.size() <= 2) return 0;
        int ans = 0;
        for (int i = 0, n = nums.size(); i < n - 2; ) {
            int j = i, d = nums[i + 1] - nums[i];
            while (j + 1 < n && nums[j + 1] - nums[j] == d) ++j;
            int len = j - i + 1, a0 = 1, an = len - 3 + 1;
            //符合条件(长度>=3且<=len)的等差子数组的数量
            int cnt = (a0 + an) * an / 2;
            ans += cnt;
            i = j;
        } 
        return ans;
   }
};

时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$ 。运行效率如下：

执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户
内存消耗：7.2 MB, 在所有 C++ 提交中击败了48.81% 的用户

解法2 动态规划

设数组 dp[] ，其中的 dp[i] 代表以 nums[i] 为结尾的等差子数组的数目，本题答案为所有 dp[i] 之和。容易得到递推公式：
$$\{\begin{array}{ll}dp[i]=dp[i?1]+1& ifnums[i]?nums[i?1]==nums[i?1]?nums[i?2]\\ dp[i]=0& else.\end{array}$$

原理很简单，在等差子数组 arr 之后添加一个元素 nums[i] ：

• 可行时，等差子数组的总个数将新增 arr 中等差子数组的个数再加一，即 nums[i] 之前的等差子数组（长度大于等于 3 ）均向后延伸到 nums[i] ，nums[i] 还和 nums[i - 2], nums[i - 1] 组成新的等差子数组；
• 不可行时，以 nums[i] 结尾的等差子数组的数目为零。

代码如下：

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        if (nums.size() <= 2) return 0;
        int n = nums.size(), ans = 0;
        vector<int> dp(n); //dp[i]为以nums[i]结尾的等差数组的数目
        for (int i = 2; i < n; ++i) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                dp[i] = dp[i - 1] + 1;
                ans += dp[i];
            } 
        } 
        return ans;
   }
};

时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$ 。运行效率如下所示：

执行用时：4 ms, 在所有 C++ 提交中击败了44.58% 的用户
内存消耗：7.2 MB, 在所有 C++ 提交中击败了41.60% 的用户

由于 dp[i] 只和前一个状态 dp[i - 1] 有关，而且不用记录下 dp[i - 1] ，我们可以优化掉 dp[] 而代之以一个状态变量 dp ：

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        if (nums.size() <= 2) return 0;
        int n = nums.size(), ans = 0, dp = 0;
        for (int i = 2; i < n; ++i) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                ++dp; //dp[i]=dp[i-1]+1;
                ans += dp;
            } else dp = 0;
        } 
        return ans;
   }
};

时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$ 。运行效率如下所示：

执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户
内存消耗：7.1 MB, 在所有 C++ 提交中击败了59.52% 的用户