算法leetcode

力扣1630-等差子数组

字数统计: 1.1k字   |   阅读时长: 4分
, ,

摘要: 力扣1630-等差子数组，等差数列的判定

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

题目

1630. 等差子数组

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

示例 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]

题解

算法1：排序

对每一次查询 [l, r]，将 nums[l..r] 排序，然后遍历每一对相邻数字，看它们的差是否为同一个值。

代码 (C++)

$O(mn\log{n})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
        int m = l.size();
        vector<bool> result(m);
        for(int i = 0; i < m; ++i)
        {
            int left = l[i], right = r[i];
            result[i] = true;
            if(left + 1 == right)
                continue;
            vector<int> cand(nums.begin() + left, nums.begin() + right + 1);
            sort(cand.begin(), cand.end());
            int d = cand[1] - cand[0];
            for(int j = 2; j < (int)cand.size(); ++j)
                if(cand[j] - cand[j - 1] != d)
                {
                    result[i] = false;
                    break;
                }
        }
        return result;
    }
};

算法2：数学

对每一次查询 [l, r]，考察 nums[l..r]，其元素个数为 r - l + 1，遍历一轮得到其最大值 maxx、最小值 minx。

那么如果 nums[l..r] 可以重排为等差数列，则公差应该为 $d = \frac{maxx - minx}{r - l}$，如果 d 不为整数，则直接返回 false。

如果 d 为整数，那么 nums[l..r] 这 r - l + 1 个数，应该分别为 $minx + kd$，其中 $k = 0, 1, \cdots, r - l$。

不用排序直接遍历一遍 nums[l..r]，每遍历到一个数字 nums[i]，首先判断是否是哈希表中的数字，如果不是的话返回 false，否则看哈希表是否记录了该数字之前出现过，如果出现过，则也返回 false。

代码 (C++)

$O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
        int m = l.size();
        vector<bool> result(m, true);
        for(int i = 0; i < m; ++i)
        {
            int left = l[i], right = r[i];
            result[i] = true;
            if(left + 1 == right)
                continue;
            int maxx = *max_element(nums.begin() + left, nums.begin() + right + 1);
            int minx = *min_element(nums.begin() + left, nums.begin() + right + 1);
            if((maxx - minx) % (right - left) != 0)
            {
                result[i] = false;
            }
            else if(maxx != minx)
            {
                int d = (maxx - minx) / (right - left);
                unordered_map<int, int> mapping;
                for(int k = 0; k <= (right - left); ++k)
                    mapping[minx + k * d] = 0;
                for(int j = left; j <= right; ++j)
                {
                    if(mapping.count(nums[j]) == 0 || mapping[nums[j]] > 0)
                    {
                        result[i] = false;
                        break;
                    }
                    mapping[nums[j]] = 1;
                }
            }
        }
        return result;
    }
};
Share