arrays - 子数组由可以按连续顺序排列的数字组成。

Question

找到长度为W的子数组，该子数组由可以连续排列的数字组成。对于 ex- {4,5,1,5,7,6,8,4,1} 且 W 为 5，输出可以是 -{5,7,6,8,4}..

Answer 1

长度为 W 的连续子数组包含连续(但未排序)序列，具有三个可用于构造有效算法的属性:

1. 子数组中有 W 个元素。
2. 子数组中最大和最小数字之间的差异为 W-1。
3. 子数组中没有重复元素。

算法应该将两个指针前进到输入数组，并检查这些指针之间的子数组是否满足这三个属性。

1. 将两个指针前移，使指针之间的差值等于 W。
2. 在推进第一个指针的同时，将相应的数组元素放入集合(以控制重复)和最小-最大队列(以控制数字范围)中。
3. 如果在集合中发现重复元素，则将第二个指针前进到第一个重复元素的位置，从而更新集合和队列。
4. 在最大值和最小值之间的差值保持大于W-1时前进第二个指针，从集合和队列中删除相应的元素。
5. 当所有三个属性都为 true 时停止。

最小-最大队列可以实现为一对最小-最大堆栈，如 this answer 中所述。 。集合可以实现为散列集(给出算法的预期复杂度为 O(n))，或者实现为二叉搜索树(给出最坏情况复杂度为 O(n log(n)))，或者实现为以下组合的组合:位集和环形缓冲区 - 仅保留位，对应于队列报告的最小值和最大值之间的元素(给出 O(n) 最坏情况复杂性)。

输入数组 {42,10,7,4,5,1,5,7,6,8,4,1} 和 W=5 的示例(“:”标记环形缓冲区的开始)。

subarray       bitset        rb_start     min  max
42             :1 0 0 0 0    42           42   42
10             :1 0 0 0 0    10           10   10 (with 42, max-min>W-1)
10 7            1 0:1 0 0    7            7    10
7 4             0 0 1 0:1    4            4    7  (with 10, max-min>W-1)
7 4 5           1 0 1 0:1    4            4    7
4 5 1           1:1 0 0 1    1            1    5  (with 7, max-min>W-1)
1 5             1:1 0 0 0    1            1    5  (5 is a duplicate)
5 7            :1 0 1 0 0    5            5    7  (with 1, max-min>W-1)
5 7 6          :1 1 1 0 0    5            5    7
5 7 6 8        :1 1 1 1 0    5            5    8
5 7 6 8 4       1 1 1 1:1    4            4    8  (success)