等差子数组

难度: Medium

如果一个数列由至少两个元素组成，且每两个连续元素之间的差值都相同，那么这个序列就是 等差数列 。更正式地，数列 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.length
m == l.length
m == r.length
2 <= n <= 500
1 <= m <= 500
0 <= l[i] < r[i] < n
-10⁵ <= nums[i] <= 10⁵

Submission

运行时间: 59 ms

内存: 16.2 MB

class Solution:
    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:
        n = len(l)
        ans = [False]*n
        for i in range(n):
            start = l[i]
            end = r[i]
            #tmp = deepcopy(nums[start:end+1])
            tmp = nums[start:end+1]
            tmp.sort()
            d = tmp[1]-tmp[0]
            ans[i] = True
            for j in range(1,len(tmp)):
                if tmp[j]-tmp[j-1] != d:
                    ans[i] = False
                    break
        return ans

Explain

此题解的主要思路是通过遍历每个由数组 l 和 r 指定的子数组，首先对子数组进行排序，然后检查排序后的子数组是否形成等差序列。步骤如下： 1. 遍历每个查询区间（由 l 和 r 数组指定的起始和结束索引）。 2. 截取并复制相应的子数组，然后对此子数组进行排序。 3. 计算排序后子数组的第一个元素与第二个元素的差，作为等差序列的公差。 4. 遍历排序后的子数组，检查每一对连续元素的差是否等于第一步计算的公差。 5. 如果所有连续元素的差都等于公差，则该子数组是等差数列，否则不是。 6. 将结果存储在答案数组中，最后返回答案数组。

时间复杂度: O(m * k log k)，其中 k 是平均每个查询的子数组长度

空间复杂度: O(m + k)，其中 k 是子数组的最大长度

# 定义解题类
class Solution:
    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:
        n = len(l)
        ans = [False] * n  # 初始化结果列表
        for i in range(n):
            start = l[i]  # 获取当前查询的起始位置
            end = r[i]    # 获取当前查询的结束位置
            # 获取并排序子数组
            tmp = nums[start:end+1]
            tmp.sort()
            d = tmp[1] - tmp[0]  # 计算公差
            ans[i] = True
            # 检查子数组是否符合等差数列的条件
            for j in range(1, len(tmp)):
                if tmp[j] - tmp[j-1] != d:
                    ans[i] = False
                    break
        return ans

Explore

在检查子数组是否为等差数列时，排序可以简化检查过程。排序后，子数组的元素将以严格的递增或递减顺序排列，这使得仅需要检查任何两个连续元素之间的差值是否相等。这种方法规避了原始数组可能的无序状态，确保了只需一次简单的线性扫描即可验证等差性质。排序后，公差的确定变得简单，因为我们可以直接取排序后的前两个元素之差作为整个子数组的公差，然后验证所有连续元素对是否满足此公差。

在排序后的子数组中，如果子数组是等差的，那么任何两个连续元素的差都应该相同。因此，计算第一对元素的差值可以有效地确定预期的公差，用以后续验证整个数组的等差性质。这种方法在所有元素相等的情况下依然有效，因为公差将为零。然而，如果子数组长度小于2（虽然题目条件指定至少两个元素），则无法使用这一方法确定公差。此外，如果输入数据错误或处理过程中出现索引错误，也可能导致计算错误或异常。

如果子数组只有两个元素，按照当前算法逻辑，我们首先会计算这两个元素的差值作为公差，然后在循环中再次检查这两个元素是否符合这一公差。实际上，对于只有两个元素的子数组，一旦确定了排序和计算了公差，就可以直接确认它是等差的，无需进一步循环。因此，可以对算法进行优化，直接在检测到子数组长度为2时返回True，省去不必要的循环检查，从而提高效率。