1. 题目背景与核心需求解析套手镯是蓝桥杯2024年国赛B组的一道典型双指针算法题题目编号P10913。这道题考察选手对滑动窗口技巧的掌握程度属于普及/提高-难度级别。题目描述通常为给定一个由不同材质组成的手镯环要求找出满足特定条件的最长子序列。这类问题的核心在于如何在O(n)时间复杂度内完成序列扫描。直接暴力解法需要O(n^2)的时间复杂度对于n较大的情况比如n10^5必然超时。而双指针算法能够将时间复杂度优化到O(n)这正是该题设计的精妙之处。提示蓝桥杯国赛题往往在基础算法上设置巧妙的变形需要选手真正理解算法本质而非死记模板。2. 双指针算法深度剖析2.1 基础双指针模型双指针算法主要有两种实现模式快慢指针常用于链表问题滑动窗口适用于连续子序列问题本题明显属于第二种情况。滑动窗口的典型特征是维护一个区间[left, right]通过调整左右边界来寻找最优解。其核心代码框架如下int left 0, right 0; while (right n) { // 扩展右边界 window.add(s[right]); right; while (window需要收缩的条件) { // 收缩左边界 window.remove(s[left]); left; } // 在此更新答案 res max(res, right - left); }2.2 本题的特殊处理根据类似题目经验套手镯问题通常有以下变种限制子序列中不同材质的最大种类数要求子序列中某种材质的最小出现次数环形数组的处理手镯是首尾相接的对于环形数组常规处理技巧是将原数组复制一份接在后面然后在新数组上做线性处理特别注意最终答案不能超过原数组长度n3. 完整解题代码实现3.1 数据结构选择使用哈希表(unordered_map)来记录窗口内各材质的出现次数是最佳选择插入、删除、查询都是O(1)时间复杂度可以方便地获取当前窗口内的材质种类数#include iostream #include vector #include unordered_map using namespace std; int solve(vectorint materials, int k) { unordered_mapint, int count; int left 0, max_len 0; int n materials.size(); // 环形处理将数组延长一倍 materials.insert(materials.end(), materials.begin(), materials.end()); for (int right 0; right 2 * n; right) { count[materials[right]]; // 当材质种类超过k时收缩窗口 while (count.size() k) { count[materials[left]]--; if (count[materials[left]] 0) { count.erase(materials[left]); } left; } // 更新答案且不超过原长度 if (right - left 1 n) { max_len max(max_len, right - left 1); } } return max_len; }3.2 复杂度分析时间复杂度O(2n) O(n)每个元素最多被访问两次加入和移除窗口空间复杂度O(k)哈希表最多存储k1个键值对4. 关键测试用例与调试技巧4.1 必须考虑的边界情况所有材质都相同的情况输入[1,1,1,1], k1输出4k大于材质种类数输入[1,2,3,4], k5输出4环形特性测试输入[1,2,3,1,2], k2输出5因为可以选整个环形数组4.2 常见错误与修正忘记处理环形特性错误表现对于[1,2,1]这样的输入可能漏掉跨越首尾的最优解修正方法按3.1节所示将数组延长窗口收缩条件错误典型错误while(count.size() k)正确应该是while(count.size() k)答案长度超过n必须添加right - left 1 n的条件判断5. 算法优化与扩展思考5.1 空间优化方案如果材质编号的范围已知且较小比如0-1000可以用数组代替哈希表int count[1001] {0};这样可以将空间复杂度从O(k)降到O(1)但仅适用于特定场景。5.2 相似题目推荐无重复字符的最长子串LeetCode 3至多包含K个不同字符的最长子串LeetCode 340替换后的最长重复字符LeetCode 424水果成篮LeetCode 904这些题目都是滑动窗口的经典应用建议按顺序练习以掌握算法变种。6. 竞赛技巧与实战建议模板化编码提前准备好双指针的代码模板比赛时快速修改变量命名使用left/right比i/j更易读减少边界错误调试输出在竞赛环境中可以打印窗口状态辅助调试cout [ left , right ]: ; for(int ileft; iright; i) cout materials[i] ; cout endl;时间分配这类题目应在30分钟内完成包括编码和测试经验分享在实际比赛中我通常会先写暴力解法验证思路正确性再优化为双指针解法。虽然多花5分钟但能避免思路错误导致的更大时间浪费。