1630. 等差子数组
难度中等9收藏分享切换为英文接收动态反馈
如果一个数列由至少两个元素组成，且每两个连续元素之间的差值都相同，那么这个序列就是 等差数列 。更正式地，数列 s 是等差数列，只需要满足：对于每个有效的 i ， s[i+1] - s[i] == s[1] - s[0] 都成立。
例如，下面这些都是 等差数列 ：
1 | 1, 3, 5, 7, 9 |
下面的数列 不是等差数列 ：
1 | 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：
1 | 输入：nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5] |
示例 2：
1 | 输入：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] |
提示：
n == nums.lengthm == l.lengthm == r.length2 <= n <= 5001 <= m <= 5000 <= l[i] < r[i] < n-105 <= nums[i] <= 105
非暴力思路
- 将区间转换成二维数组，然后按照区间的 $start$ 从小到大排序，如果 $start$ 相同，就按照 $end$ 从小到大排序
- 根据区间的大小进行二分查找插入排序（使用LinkedList），并记录插入的数据（便于删除）
- 维护新区间的元素
- 判断区间是否是等差序列
- 删除元素，进行区间变化
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98class Solution {
public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
int qLen = l.length;
if (qLen == 0) return new ArrayList<>();
int[][] query = new int[l.length][3];
for (int i = 0; i < qLen; i++) {
query[i][0] = l[i];// 区间的开始
query[i][1] = r[i];// 区间的结束
query[i][2] = i;// 当前查询的index
}
// 对query按照区间开始从小到大排序
Arrays.sort(query, new Comparator<int[]>() {
public int compare(int[] o1, int[] o2) {
return o1[0] == o2[0] ? Integer.compare(o1[1], o2[1]) : Integer.compare(o1[0], o2[0]);
}
});
// 双端队列维护入队的顺序
Deque<int[]> queue = new LinkedList<>();
// list维护查询窗口中的元素
List<int[]> list = new LinkedList<>();
// 初始化查询窗口
for (int i = query[0][0]; i <= query[0][1]; i++) {
int[] val = new int[]{nums[i], i};
insert(list, val);
queue.offer(val);
}
// 结果数组
Boolean[] res = new Boolean[qLen];
// 判断第一个窗口是否满足等差条件
res[query[0][2]] = judge(list);
for (int i = 1; i < qLen; i++) {
// 新窗口与旧窗口之间的起始位置的差
int startDiff = query[i][0] - query[i - 1][0];
// 窗口中应该有的数字的数量
int interval = query[i][1] - query[i][0] + 1;
// 根据新窗口与旧窗口之间的起始位置的差从左边界删除元素
for (int j = 0; j < startDiff; j++) {
if (!queue.isEmpty()) {
int[] added = queue.poll();
list.remove(added);
}
}
// 当前窗口中剩余的数量
int size = list.size();
// 如果interval - size大于0，说明新窗口中还有值没有添加进来，继续添加元素
for (int j = 0; j < interval - size; j++) {
int index = j + query[i][0] + size;
int[] val = new int[]{nums[index], index};
queue.add(val);
insert(list, val);
}
// 如果interval - size小于0，说明当前窗口中元素的数量多于窗口中元素的真实数量，应该从右边界删除元素
for (int j = 0; j < -(interval - size); j++) {
int[] added = queue.pollLast();
list.remove(added);
}
// 判断当前窗口是否满足等差
res[query[i][2]] = judge(list);
}
ArrayList<Boolean> resList = new ArrayList<Boolean>(res.length);
Collections.addAll(resList, res);
return resList;
}
// 二分查找插入排序
public void insert(List<int[]> list, int[] val) {
int l = 0, r = list.size() - 1, mid = 0;
while (l <= r) {
mid = l + (r - l) / 2;
int value = list.get(mid)[0];
if (value == val[0]) {
list.add(mid, val);
return;
} else if (value < val[0]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
list.add(l, val);
}
// 判断数组是否满足等差数列条件
public boolean judge(List<int[]> list) {
if (list.size() <= 2) return true;
int diff = list.get(1)[0] - list.get(0)[0];
for (int i = 2; i < list.size(); i++) {
if (list.get(i)[0] - list.get(i - 1)[0] != diff) return false;
}
return true;
}
}
暴力法
截取对应的子数组，排序，判断是否是等差数组
1 | public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) { |
