等差数列划分
难度:
标签:
题目描述
如果一个数列 至少有三个元素 ,并且任意两个相邻元素之差相同,则称该数列为等差数列。
- 例如,
[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
代码结果
运行时间: 24 ms, 内存: 16.3 MB
/*
* Problem Statement:
* An arithmetic sequence is defined as a sequence of at least three elements where the difference between consecutive elements is constant.
* Given an integer array nums, return the number of all the arithmetic subarrays of nums.
* A subarray is a contiguous subsequence of the array.
*
* Approach using Java Streams:
* 1. Initialize a variable to store the count of arithmetic subarrays.
* 2. Use IntStream to iterate through the array and find all subarrays with at least 3 elements.
* 3. For each subarray, check if it forms an arithmetic sequence by comparing the difference between consecutive elements.
* 4. Count all valid arithmetic subarrays.
*/
import java.util.stream.IntStream;
public class ArithmeticSubarraysStream {
public int numberOfArithmeticSlices(int[] nums) {
int[] count = {0};
IntStream.range(0, nums.length - 2).forEach(i -> {
int diff = nums[i + 1] - nums[i];
IntStream.range(i + 2, nums.length).takeWhile(j -> nums[j] - nums[j - 1] == diff).forEach(j -> count[0]++);
});
return count[0];
}
}
解释
方法:
这个题解使用动态规划来解决问题。定义状态 dp[i] 表示以 nums[i] 结尾的等差数列的个数。当 nums[i-1] * 2 == nums[i] + nums[i-2] 时,说明 nums[i-2], nums[i-1], nums[i] 构成等差数列,此时 dp[i] = dp[i-1] + 1,即在前一个状态的基础上再加上 nums[i]。最后对 dp 数组求和即可得到所有的等差数列个数。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在动态规划中定义的状态 dp[i] 代表什么意义,为什么它能够帮助解决问题?
▷🦆
状态转移方程 dp[i] = dp[i-1] + 1 是如何得来的,它背后的逻辑是什么?
▷🦆
这种动态规划方法为什么从下标2开始遍历数组,从下标0或1开始会有什么问题?
▷🦆
题解中提到当 nums[i-1] * 2 == nums[i] + nums[i-2] 时才进行状态更新,这个条件是如何确保子数组确实是等差数列的?
▷相关问题
等差数列划分 II - 子序列
给你一个整数数组 nums
,返回 nums
中所有 等差子序列 的数目。
如果一个序列中 至少有三个元素 ,并且任意两个相邻元素之差相同,则称该序列为等差序列。
- 例如,
[1, 3, 5, 7, 9]
、[7, 7, 7, 7]
和[3, -1, -5, -9]
都是等差序列。 - 再例如,
[1, 1, 2, 5, 7]
不是等差序列。
数组中的子序列是从数组中删除一些元素(也可能不删除)得到的一个序列。
- 例如,
[2,5,10]
是[1,2,1,2,4,1,5,10]
的一个子序列。
题目数据保证答案是一个 32-bit 整数。
示例 1:
输入:nums = [2,4,6,8,10] 输出:7 解释:所有的等差子序列为: [2,4,6] [4,6,8] [6,8,10] [2,4,6,8] [4,6,8,10] [2,4,6,8,10] [2,6,10]
示例 2:
输入:nums = [7,7,7,7,7] 输出:16 解释:数组中的任意子序列都是等差子序列。
提示:
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1