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