Medium

题目描述

如果一个数字序列由至少两个元素组成，且每两个连续元素之间的差值都相同，则称该序列为等差数列。更正式地，当且仅当对于所有有效的 i，都有 s[i+1] - s[i] == s[1] - s[0] 时，序列 s 才是等差数列。

例如，这些都是等差数列：

  • 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，其中 answer[i] 为 true 当且仅当子数组 nums[l[i]], nums[l[i]+1], …, nums[r[i]] 可以重新排列形成等差数列。

示例 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^5 <= nums[i] <= 10^5

解题思路

解题思路

这道题要判断给定范围内的子数组能否重新排列成等差数列。关键在于理解等差数列的性质：

  1. 核心观察：一组数字能组成等差数列当且仅当排序后的序列是等差数列
  2. 等差数列判断：排序后相邻元素的差值必须相等

解法分析

方法一：排序 + 逐一检查（推荐）

  • 对每个查询范围提取子数组
  • 排序后检查相邻元素差值是否相等
  • 时间复杂度较低，实现简单

方法二：数学优化

  • 利用等差数列性质：最大值、最小值、长度确定差值
  • 检查是否存在重复元素且能形成完整等差数列
  • 适用于特定场景，但实现复杂度较高

算法步骤：

  1. 遍历每个查询 [l[i], r[i]]
  2. 提取对应子数组并排序
  3. 检查排序后数组是否为等差数列：
    • 长度至少为2
    • 计算公差 d = sorted[1] - sorted[0]
    • 验证所有相邻元素差值都等于 d

这种方法直观易懂，代码简洁，适合解决该问题。

代码实现

class Solution {
public:
    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
        vector<bool> result;
        
        for (int i = 0; i < l.size(); i++) {
            vector<int> subarray(nums.begin() + l[i], nums.begin() + r[i] + 1);
            sort(subarray.begin(), subarray.end());
            
            bool isArithmetic = true;
            if (subarray.size() >= 2) {
                int diff = subarray[1] - subarray[0];
                for (int j = 2; j < subarray.size(); j++) {
                    if (subarray[j] - subarray[j-1] != diff) {
                        isArithmetic = false;
                        break;
                    }
                }
            }
            
            result.push_back(isArithmetic);
        }
        
        return result;
    }
};

class Solution:
    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:
        result = []
        
        for i in range(len(l)):
            subarray = nums[l[i]:r[i]+1]
            subarray.sort()
            
            is_arithmetic = True
            if len(subarray) >= 2:
                diff = subarray[1] - subarray[0]
                for j in range(2, len(subarray)):
                    if subarray[j] - subarray[j-1] != diff:
                        is_arithmetic = False
                        break
            
            result.append(is_arithmetic)
        
        return result

public class Solution {
    public IList<bool> CheckArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        List<bool> result = new List<bool>();
        
        for (int i = 0; i < l.Length; i++) {
            int[] subarray = new int[r[i] - l[i] + 1];
            Array.Copy(nums, l[i], subarray, 0, subarray.Length);
            Array.Sort(subarray);
            
            bool isArithmetic = true;
            if (subarray.Length >= 2) {
                int diff = subarray[1] - subarray[0];
                for (int j = 2; j < subarray.Length; j++) {
                    if (subarray[j] - subarray[j-1] != diff) {
                        isArithmetic = false;
                        break;
                    }
                }
            }
            
            result.Add(isArithmetic);
        }
        
        return result;
    }
}

var checkArithmeticSubarrays = function(nums, l, r) {
    const result = [];
    
    for (let i = 0; i < l.length; i++) {
        const subarray = nums.slice(l[i], r[i] + 1);
        subarray.sort((a, b) => a - b);
        
        let isArithmetic = true;
        if (subarray.length >= 2) {
            const diff = subarray[1] - subarray[0];
            for (let j = 2; j < subarray.length; j++) {
                if (subarray[j] - subarray[j-1] !== diff) {
                    isArithmetic = false;
                    break;
                }
            }
        }
        
        result.push(isArithmetic);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × k × log k)其中 m 是查询次数，k 是子数组平均长度，排序需要 O(k log k)
空间复杂度O(k)需要额外空间存储子数组进行排序

相关题目