博客

题目大意

如果一个数列由至少两个元素组成，且每两个连续元素之间的差值都相同，那么这个序列就是 等差数列 。更正式地，数列 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 。

解题思路

第一步：判断某个区间是否是等差子数组；

• 如果区间只有一个元素，是等差子数组；
• 记录区间最大最小值，不能整除，则不是等差子数组；
• 如果最大值==最小值，则是等差子数组（元素相同）；
• 遍历子数组，判断当前元素是由最小值+多少倍的差值构成，如果倍数重复了，则不是等差子数组；
• 反之，则是等差子数组；

第二步，遍历区间即可；

class Solution{
public:
    vector<bool> checkArithmeticSubarrays(vector<int> & nums, vector<int> & l, vector<int> & r){
        int n = l.size();
        vector<bool> ans(n, false);
        for (int i = 0; i < n; ++i){
            ans[i] = check(nums, l[i], r[i]);
        }
        return ans;
    }

    bool check(vector<int> & nums, int l, int r){
        if (r - l < 2){
            return true;
        }

        int minValue = INT_MAX, maxValue = INT_MIN, tmp;
        for (int i = l; i <= r; ++i){
            if (nums[i] > maxValue){
                maxValue = nums[i];
            }
            if (nums[i] < minValue){
                minValue = nums[i];
            }
        }
        if ((maxValue - minValue) % (r - l) != 0){
            return false;
        }
        if (minValue == maxValue){
            return true;
        }
        int diff = (maxValue - minValue) / (r - l);

        unordered_set<int> myset;
        for (int i = l; i <= r; ++i){
            tmp = nums[i] - minValue;
            if (tmp % diff != 0){
                return false;
            }
            tmp /= diff;
            if (myset.find(tmp) != myset.end()){
                return false;
            }
            myset.insert(tmp);
        }
        return true;
    }
};