蓝桥杯‘子串简写’题从暴力枚举到二分优化的思维跃迁第一次参加蓝桥杯时我盯着那道子串简写的题目整整半小时毫无头绪。直到比赛结束前才勉强写出暴力解法结果自然是超时。后来复盘时才恍然大悟原来只需要一个简单的二分查找就能让效率提升百倍。本文将带你完整重现这个思维升级的过程。1. 问题本质与暴力解法剖析题目要求统计字符串中所有满足特定条件的子串数量子串首字符为c1尾字符为c2且长度≥k。表面看这似乎需要检查所有可能的子串组合但深入分析会发现隐藏的优化空间。暴力解法的核心代码如下for(int i 0; i s.size(); i) { if(s[i] ! c1) continue; for(int j i 1; j s.size(); j) { if(j - i 1 k s[j] c2) ans; } }这种双重循环的时间复杂度是O(n²)当n达到10⁵时必然超时。但仔细观察会发现内层循环其实在做重复工作——每次遇到c1时都在重新扫描整个后续字符串寻找c2。暴力解法的三大痛点重复扫描对每个c1都重新检查后续所有字符无效计算即使知道后续c2的位置仍逐个检查缺乏预处理没有利用字符串的静态特性2. 优化思路的突破口关键在于发现两个重要特征c2的位置是固定的与当前c1无关对每个c2我们只需要知道前面有多少个c1满足位置差≥k-1这提示我们可以预处理记录所有c1的位置对每个c2在c1位置数组中快速统计满足条件的数量优化思路演进表思考阶段关键发现潜在解法时间复杂度初始暴力必须检查所有子串双重循环O(n²)第一次优化c2位置固定记录c1位置O(n*m)最终突破位置有序可二分二分查找统计O(n log m)3. 二分查找的精妙应用预处理阶段我们用一个数组pc1按顺序存储所有c1的位置。对于每个c2的位置j我们需要统计pc1中有多少元素≤j-k1。vectorint pc1; // 存储c1的位置 for(int i 0; i s.size(); i) { if(s[i] c1) pc1.push_back(i); if(s[i] c2) { if(i - k 1 0 || pc1.empty()) continue; int target i - k 1; // 二分查找pc1中≤target的最大索引 int l 0, r pc1.size() - 1; while(l r) { int mid (l r 1) 1; if(pc1[mid] target) l mid; else r mid - 1; } if(pc1[l] target) ans (l 1); } }这段代码有几个关键点pc1数组天然有序满足二分查找前提使用mid (l r 1) 1确保不会死循环最终检查pc1[l] target避免边界错误4. 复杂度分析与性能对比假设字符串中c1出现m次c2出现n次方法时间复杂度空间复杂度10⁵数据耗时暴力O(n²)O(1)10秒预处理线性扫描O(n*m)O(m)~1秒预处理二分查找O(n log m)O(m)0.01秒实际测试中当n10⁵时暴力解法无法在合理时间内完成二分优化版本仅需约15ms5. 调试技巧与常见陷阱实现二分查找时容易遇到以下问题边界条件处理空pc1数组情况所有c1位置都大于target所有c1位置都小于target二分查找变体选择这里需要找最后一个≤target的元素使用mid (l r 1) 1而非mid (l r) 1循环条件while(l r)而非while(l r)调试小技巧先写暴力解法作为正确性验证对小样例打印pc1数组和二分过程测试极端情况k1全c1全c2等6. 思维拓展与其他应用场景这种预处理二分统计的模式适用于许多字符串问题区间统计问题统计满足某种区间条件的元素对最近邻查找快速找到距离某个位置最近的特定字符频率统计统计特定字符在某个区间内的出现次数例如LeetCode 792题匹配子序列就可以用类似的思路将时间复杂度从O(n²)优化到O(n log m)。