1630.等差子数组

发表于 更新于 分类于 阅读次数：

前言

题目来自LeetCode：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：

输入：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] 。

提示：

  • 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

题解

通过分析n,m的大小，暴力解决，每次确定左右边界，把数组考出来排序，遍历，判断。时间复杂度O(mnlogn)。
优化：可以把排序那部分进行优化，其实判断一个数列是否为等差数列，并不需要这段序列有序，只要找到公差即可。如果一段序列是等差数列，那么每个数与最小值之间的差值肯定为公差的k倍，所以，只需遍历一遍序列，找到最大，最小值，就能计算出公差d = (max - min) / (长度 - 1)，最后只需再遍历一次，判断每个数与最小值的差值是否为公差的k倍即可（判断一下有没有相同的数，如果有且最大值与最小值不相等，则一定不是等差数列）。
时间复杂度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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class Solution {
    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        int len = l.length;
        List<Boolean> res = new ArrayList<>();
        //遍历边界数组
        for(int i = 0; i < len; i++){
            int t_l = l[i];
            int t_r = r[i];
            int t_len = t_r - t_l + 1;
            //如果所求序列长度小于2，那么必定是等差数组
            if(t_len <= 2){
                res.add(true);
                continue;
            }

            //第一种方法O(mnlogn)
            int[] t = new int[t_len];
            //复制数组
            System.arraycopy(nums, t_l, t, 0, t_len);
            //排序
            Arrays.sort(t);
            //找到公差
            int d = t[1] - t[0];
            boolean f = true;
            //判断间隔是否为公差d
            for(int j = 2; j < t_len; j++){
                if(t[j] - t[j - 1] != d){
                    f = false;
                    break;
                }
            }
            res.add(f);

            /*
            //第二种方法O(mn)
            int max = nums[t_l], min = nums[t_l];
            //找到最大最小值
            for(int j = t_l; j <= t_r; j++){
                max = max > nums[j] ? max : nums[j];
                min = min < nums[j] ? min : nums[j];
            }
            //如果最大最小值相等，则证明这个序列全都相等，自然是等差数列
            if(max == min){
                res.add(true);
                continue;
            }
            //如果公差不是正数，则一定不是等差数列
            if((max - min) % (t_len - 1) != 0){
                res.add(false);
                continue;
            }
            //求公差
            int d = (max - min) / (t_len - 1);
            boolean f = true;
            //标记数组，判断是否有重复的数
            boolean[] exist = new boolean[t_len];
            for(int j = t_l; j <= t_r; j++){
                if((nums[j] - min) % d != 0){
                    f = false;
                    break;
                }
                //标记出现过的数
                int t = (nums[j] - min) / d;
                if(exist[t]){
                    f = false;
                    break;
                }
                exist[t] = true;
            }
            res.add(f);
            */
        }
        return res;
        
    }
}