0413. Arithmetic Slices
=======================
题目信息
--------
:题号: 0413
:难度: Medium
:主题: 连续子数组、等差序列、长度下限、区间计数
:原题: `LeetCode 0413 `_
:重点: 子数组必须连续且长度至少为 3、相邻差值全部相同、不同起止下标分别计数
题目重述
--------
给定整数数组 ``nums``,统计其中有多少个连续子数组是等差数列。一个子数组只有在长度至少为 3,并且任意相邻两项的差值都相同时,才算一个算术切片。
``nums.length`` 位于 ``[1, 5000]``,每个元素位于 ``[-1000, 1000]``。子数组必须对应原数组中的连续下标区间;即使两个子数组包含的数值序列相同,只要起止下标不同,也应分别计数。
自建示例
--------
等差段后接一个破坏差值的元素:
.. code-block:: text
输入:nums = [2, 4, 6, 8, 11]
输出:3
解释:合法子数组是 [2,4,6]、[4,6,8] 和 [2,4,6,8];包含 11 的长度至少为 3 的区间都不是等差数列。
全部元素相同:
.. code-block:: text
输入:nums = [5, 5, 5, 5, 5]
输出:6
解释:长度为 3、4、5 的连续子数组分别有 3、2、1 个,差值均为 0,总数为 6。
按右端点统计新增加的切片
--------------------------
扫描到下标 ``i`` 时,如果 ``nums[i] - nums[i-1]`` 与前一个差值相同,那么以 ``i`` 结尾的等差切片数量会比以 ``i-1`` 结尾多一个:在原有每个切片前面再延长一项,并新增刚好长度为 3 的切片。令 ``ending`` 表示这个数量,差值中断时归零。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int numberOfArithmeticSlices(std::vector& nums) {
long long answer = 0;
int ending = 0;
for (int i = 2; i < static_cast(nums.size()); ++i) {
if (nums[i] - nums[i - 1]
== nums[i - 1] - nums[i - 2]) {
++ending;
answer += ending;
} else {
ending = 0;
}
}
return static_cast(answer);
}
};
代码分析
--------
``ending`` 在连续等差段中依次为 1、2、3……,分别代表以当前下标结尾、长度至少 3 的切片数;中断后不能把前段延伸过来。每个相邻差只比较一次,时间复杂度为 ``O(n)``,额外空间为 ``O(1)``。