蓝桥杯试题：二分查找

一、问题描述

给定 n 个数形成的一个序列 a，现定义如果一个连续子序列包含序列 a 中所有不同元素，则该连续子序列便为蓝桥序列，现在问你，该蓝桥序列长度最短为多少？

例如 1 2 2 2 3 2 2 1，包含 3 个不同的数 1,2,3，而 3 2 2 1 符合题目要求，因此答案为 4。

连续子序列：从序列 a 中选取若干个连续的数形成一个序列叫连续子序列。

输入格式

第一行输入一个整数 n，表示序列长度。

第二行输入 n 个元素。

输出格式

输出一个整数，表示最短的蓝桥序列长度。

样例输入

8
1 2 2 2 3 2 2 1

样例输出

4

二、代码展示 

import java.util.*;public class 全部都有的子序列_二分_滑动窗口 {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n= sc.nextInt();int []arr=new int[n];Set<Integer> set=new HashSet<>();for (int i = 0; i < n; i++) {arr[i]= sc.nextInt();set.add(arr[i]);}int l=0,r=n;int m=set.size();//set存储不重复的数字while(l<r){int mid=(l+r)/2;if(check(mid,arr,m)) r=mid;else l=mid+1;}System.out.println(l);}public static boolean check(int mid,int []arr,int m){//滑动窗口求解int n=arr.length;int []f=new int[1001];//记录出现频率int l=0,r=0;//双指针int ans=0;//统计当前窗口的不同元素数量while(r<n) {//右指针没有到达数组最右边f[arr[r]]++;//记录一个数的频率if(f[arr[r]]==1){ ans++;}if(r-l+1>mid) {//当区间距离>mid,说明此时并没有满足ans>=mf[arr[l]]--;//左指针对应减一if(f[arr[l]]==0){//说明之前只有一个,减去后变成零,这个时候一个数字消失,对应的ans应减一ans--;}l++;//左指针右移}r++;//右指针一直右移if(ans>=m) return true;}return false;}
}

这段代码的目标是找到数组中最短的连续子序列，该子序列包含数组中所有不同的元素。采用二分查找结合滑动窗口的方法，高效地确定最小长度。

代码结构

1. 主函数：

   • 读取输入数组，并用集合统计不同元素的数量m。

   • 使用二分查找确定最小窗口长度，初始范围[0, n]。

   • 每次计算中间值mid，调用check函数验证是否存在长度为mid的窗口满足条件。

   • 根据验证结果调整二分边界，最终输出最小长度l。

2. check函数：

   • 使用滑动窗口和频率数组，判断是否存在长度不超过mid的子序列包含所有m个不同元素。

   • 维护窗口的左右指针l和r，动态调整窗口大小。

   • 统计窗口内不同元素的数量ans，若达到m则返回true。

详细步骤解释

1. 主函数逻辑

• 输入处理：读取数组，并用HashSet统计不同元素的数量m。

• 二分查找初始化：左边界l设为0（最小可能长度），右边界r设为数组长度n（最大可能长度）。

• 二分过程：

  • 计算中间值mid = (l + r) / 2。

  • 调用check(mid, arr, m)判断是否存在长度为mid的窗口。

  • 若存在，说明答案可能更小，调整右边界r = mid；否则调整左边界l = mid + 1。

• 终止条件：当l >= r时，l即为最小窗口长度。

2. check函数逻辑

• 初始化：频率数组f记录元素出现次数，双指针l和r初始为0，ans统计当前窗口的不同元素数量。

• 滑动窗口过程：

  1. 右指针扩展：r右移，增加元素频率。若元素首次出现，ans加1。

  2. 窗口大小控制：当窗口长度超过mid时，左指针右移，减少对应元素频率。若元素频率减至0，ans减1。

  3. 条件检查：每次调整后，若ans >= m，立即返回true（存在满足条件的窗口）。

• 遍历结束：若未找到满足条件的窗口，返回false。

关键点分析

• 二分查找的应用：利用答案的单调性（若长度为k可行，则更大长度必然可行），将时间复杂度优化至O(n log n)。

• 滑动窗口的灵活性：不固定窗口大小，而是允许在不超过mid的范围内动态调整，一旦满足条件立即返回。

• 频率数组的作用：快速统计窗口内不同元素的数量，通过增减频率判断元素是否存在于当前窗口。

示例说明

假设数组为[1, 2, 3, 1, 2, 3, 4]，不同元素数量m=4。

• 二分初始范围[0,7]，第一次mid=3，检查是否存在长度为3的窗口包含4个不同元素（显然不可能）。

• 调整边界，最终找到最小长度为4（如子序列[3, 1, 2, 4]或[1, 2, 3, 4]）。

总结

该算法通过二分查找快速缩小搜索范围，结合滑动窗口高效验证，确保在合理时间复杂度内找到最优解。核心在于理解二分与滑动窗口的协同作用，以及频率数组维护窗口状态的技巧。

详解check方法：

1. 初始化参数

频率数组f：记录当前窗口中各元素的出现次数，索引对应元素值。

双指针l和r：初始均为0，分别表示窗口的左右边界。

计数器ans：统计窗口内不同元素的数量，初始为0。

2. 扩展右指针（窗口右移）

遍历数组：右指针r从0开始逐步右移，处理每个元素。

更新频率：将arr[r]的频率f[arr[r]]加1。
f[arr[r]]++;

唯一性判断：若该元素首次出现在窗口（频率由0变1），则ans加1。
if (f[arr[r]] == 1) ans++;

3. 收缩左指针（控制窗口大小）

窗口长度检查：当窗口长度r - l + 1超过mid时，需收缩左边界。
if (r - l + 1 > mid) {
    // 调整左指针
}
左移操作：

减少左指针元素频率：f[arr[l]]--。

唯一性减少：若元素频率减至0，说明该元素不再存在于窗口，ans减1。
if (f[arr[l]] == 0) ans--;
左指针右移：l++。

4. 实时检查条件满足

完成调整后：每次右指针移动并调整窗口后，立即检查ans是否达到m（所有不同元素数量）。
if (ans >= m) return true;
提前返回：一旦满足条件，立即返回true，无需遍历整个数组。

5. 遍历结束处理

循环结束仍未满足：若遍历完数组仍未找到符合条件的窗口，返回false。

6.示例说明

以数组[1,2,3,1,2,3,4]和mid=4为例：

窗口逐步扩展至包含元素1,2,3，此时ans=3。

右指针到元素4时，窗口包含1,2,3,4（ans=4），但窗口长度5超过mid=4。

收缩左指针至索引3，窗口变为[1,2,3,4]，长度4满足条件，返回true。

边界情况处理
元素全相同：若数组元素全为5，m=1，窗口长度1即满足。

最小可能窗口：当mid=1且存在唯一元素时，直接返回true。

总结
check方法通过滑动窗口在O(n)时间内验证是否存在满足条件的子数组，结合二分查找高效定位最小长度，确保整体时间复杂度为O(n log n)。