LeetCode 题解工作台
等差子数组
如果一个数列由至少两个元素组成，且每两个连续元素之间的差值都相同，那么这个序列就是 等差数列 。更正式地，数列 s 是等差数列，只需要满足：对于每个有效的 i ， s[i+1] - s[i] == s[1] - s[0] 都成立。 例如，下面这些都是 等差数列 ： 1, 3, 5, 7, 9 7, …
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们设计一个函数 $check(nums, l, r)$，用于判断子数组 $nums[l], nums[l+1], \dots, nums[r]$ 是否可以重新排列形成等差数列。 函数 $check(nums, l, r)$ 的实现逻辑如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
如果一个数列由至少两个元素组成，且每两个连续元素之间的差值都相同，那么这个序列就是 等差数列 。更正式地，数列 s 是等差数列，只需要满足：对于每个有效的 i ， s[i+1] - s[i] == s[1] - s[0] 都成立。
例如，下面这些都是 等差数列 ：
1, 3, 5, 7, 9 7, 7, 7, 7 3, -1, -5, -9
下面的数列 不是等差数列 ：
1, 1, 2, 5, 7
给你一个由 n 个整数组成的数组 nums，和两个由 m 个整数组成的数组 l 和 r，后两个数组表示 m 组范围查询，其中第 i 个查询对应范围 [l[i], r[i]] 。所有数组的下标都是 从 0 开始 的。
返回 boolean 元素构成的答案列表 answer 。如果子数组 nums[l[i]], nums[l[i]+1], ... , nums[r[i]] 可以 重新排列 形成 等差数列 ，answer[i] 的值就是 true；否则answer[i] 的值就是 false 。
示例 1：
输入：nums =[4,6,5,9,3,7], l =[0,0,2], r =[2,3,5]输出：[true,false,true]解释： 第 0 个查询，对应子数组 [4,6,5] 。可以重新排列为等差数列 [6,5,4] 。 第 1 个查询，对应子数组 [4,6,5,9] 。无法重新排列形成等差数列。 第 2 个查询，对应子数组[5,9,3,7] 。可以重新排列为等差数列[3,5,7,9] 。
示例 2：
输入：nums = [-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10], l = [0,1,6,4,8,7], r = [4,4,9,7,9,10] 输出：[false,true,false,false,true,true]
提示：
n == nums.lengthm == l.lengthm == r.length2 <= n <= 5001 <= m <= 5000 <= l[i] < r[i] < n-105 <= nums[i] <= 105
解题思路
方法一：数学 + 模拟
我们设计一个函数 ，用于判断子数组 是否可以重新排列形成等差数列。
函数 的实现逻辑如下：
- 首先，我们计算子数组的长度 ，并将子数组中的元素放入集合 中，方便后续的查找；
- 然后，我们获取子数组中的最小值 和最大值 ，如果 不能被 整除，那么子数组不可能形成等差数列，直接返回 ；否则，我们计算等差数列的公差 ；
- 接下来从 开始，依次计算等差数列中第 项元素，如果第 项元素 不在集合 中，那么子数组不可能形成等差数列，直接返回 ；否则，当我们遍历完所有的元素，说明子数组可以重新排列形成等差数列，返回 。
在主函数中，我们遍历所有的查询，对于每个查询 和 ，我们调用函数 判断子数组是否可以重新排列形成等差数列，将结果存入答案数组中。
时间复杂度 ，空间复杂度 。其中 和 分别为数组 的长度以及查询的组数。
class Solution:
def checkArithmeticSubarrays(
self, nums: List[int], l: List[int], r: List[int]
) -> List[bool]:
def check(nums, l, r):
n = r - l + 1
s = set(nums[l : l + n])
a1, an = min(nums[l : l + n]), max(nums[l : l + n])
d, mod = divmod(an - a1, n - 1)
return mod == 0 and all((a1 + (i - 1) * d) in s for i in range(1, n))
return [check(nums, left, right) for left, right in zip(l, r)]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m * n) since each of the m queries may scan up to n elements. Space complexity is O(n) to store the elements of the current subarray in a hash set for quick lookup. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Check whether subarray differences are uniform rather than sorting all elements immediately.
- question_mark
Expect O(n) scanning per query using hash sets instead of naive O(n log n) sorting.
- question_mark
Clarify constraints on l[i] and r[i] to avoid off-by-one errors when slicing subarrays.
常见陷阱
外企场景- error
Assuming subarrays are already sorted and directly checking differences.
- error
Neglecting to handle negative or zero differences when validating arithmetic property.
- error
Failing to account for subarrays of length two, which are trivially arithmetic.
进阶变体
外企场景- arrow_right_alt
Instead of checking all subarrays, determine the maximum length arithmetic subarray in a single scan.
- arrow_right_alt
Allow for at most one missing element that can be added to form an arithmetic sequence.
- arrow_right_alt
Modify the problem to check subarrays in a circular array, requiring modular index handling.