413. 等差数列划分

🟠   🔖  数组 动态规划 滑动窗口  🔗 力扣 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 arithmeticsubarrays 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

题目大意

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

• 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

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

子数组 是数组中的一个连续序列。

示例 1：

输入： nums = [1,2,3,4]

输出： 3

解释： nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

示例 2：

输入： nums = [1]

输出： 0

提示：

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

解题思路

滑动窗口 + 差分判断

1. 初始化左指针 left 和计数器 count。
2. 遍历数组，用两个指针 left 和 right 维护一个窗口，每当窗口末端元素与前一个元素的差值与窗口首端差值保持一致时，说明形成了新的等差数列，
3. 判断是否满足等差条件：
   • 若满足，对于窗口 [left, right] 中的等差数列，通过组合数学计算得知，以 right 结尾的等差子数组数量为 right - left - 1，直接累加新的等差子数组数量。
   • 否则将 left 更新为当前右指针的前一个位置 right - 1，开始尝试新的差值。
4. 返回累加结果。

复杂度分析

• 时间复杂度：O(n)，单次线性遍历数组即可完成判断。
• 空间复杂度：O(1)，仅使用常数额外空间。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function (nums) {
	let left = 0;
	let count = 0;
	for (let right = 2; right < nums.length; right++) {
		const diff = nums[left + 1] - nums[left];
		if (nums[right] - nums[right - 1] == diff) {
			count += right - left - 1;
		} else {
			left = right - 1;
		}
	}
	return count;
};

相关题目

题号	标题	题解	标签	难度	力扣
446	等差数列划分 II - 子序列		数组 动态规划	🔴	🀄️ 🔗
1630	等差子数组		数组 哈希表 排序	🟠	🀄️ 🔗
2348	全 0 子数组的数目		数组 数学	🟠	🀄️ 🔗
2414	最长的字母序连续子字符串的长度		字符串	🟠	🀄️ 🔗